Add two non-negative numbers given as decimal strings, without converting them to integers. Why can you not just use Int, and how does the carry loop work?
Predict first
What does the digit-by-digit addition print?
func addStrings(_ a: String, _ b: String) -> String {
let x = Array(a.utf8), y = Array(b.utf8)
var i = x.count - 1, j = y.count - 1, carry = 0
var digits: [UInt8] = []
while i >= 0 || j >= 0 || carry > 0 {
let s = (i >= 0 ? Int(x[i] - 48) : 0) + (j >= 0 ? Int(y[j] - 48) : 0) + carry
digits.append(UInt8(s % 10) + 48)
carry = s / 10
i -= 1; j -= 1
}
return digits.isEmpty ? "0" : String(decoding: digits.reversed(), as: UTF8.self)
}
print(addStrings("999", "1"))
print(addStrings("123456789123456789123456789", "987654321987654321"))
print(addStrings("0", "0"))
print(addStrings("", "7"))- 1000 / 123456790111111111111111110 / 0 / 7
- 999 / 123456790111111111111111110 / 0 / 7
- 1000 / 123456789111111111111111110 / 00 / 7
Mental model. Column addition on paper: you start at the right, write one digit, carry the rest, and keep going until both rows and the carry are used up.
Numbers longer than 19 digits overflow Int (and 15 or so digits lose precision in Double), which is the point of the exercise: do it the way you did at school. Walk both strings from the last digit to the first with two indices, add the digits plus a carry, append sum % 10 and keep sum / 10 as the next carry. Loop while either index is valid or a carry remains, so 999 + 1 produces the extra leading 1. The digits come out reversed, so reverse them at the end. Time O(max(m, n)), memory O(max(m, n)) for the result.
Work on Array(s.utf8) and subtract 48 (the code of “0”) instead of indexing the String: Swift strings are not random access, and s[s.index(s.startIndex, offsetBy: i)] inside a loop makes the whole thing O(n²). Edge cases to state: an empty string (treat it as zero), "0" + "0" (must give "0", not empty), different lengths, and inputs with leading zeros if the contract allows them. If asked for multiplication or for a library answer, mention Decimal and that Foundation has no built-in big integer. Reported at Meta (anonymous, unverified).
The carry produces the extra leading digit, a number far beyond Int works, zero plus zero is a single 0, and an empty string counts as zero.
Common traps
- Stopping when the shorter string ends and dropping the rest, or forgetting the final carry.
- Indexing a Swift String with offsets inside the loop. It is O(n) per access; convert to an array of bytes first.
They might follow up with
- How would you multiply two such strings? Schoolbook: multiply digit by digit into a result array of length m + n, then propagate carries.
- What if the strings can be negative or have decimals? Handle the sign separately and align the decimal points first.
Related questions
- 29.1.5 Given a string with brackets, remove the fewest parentheses to make it valid. How do you count them, and how…
- 29.1.1 Two-sum: given an array and a target, return the indices of two elements that add up to it. How do you get…
- 29.1.3 Write an Array extension that removes every element that appears in a second array. What is the complexity…
← Write an Array extension that removes every element that appears in a… Given a string with brackets, remove the fewest parentheses to make… →