Given two non-negative integers represented by strings, return the sum of both. You should not use any BigInteger library nor convert the inputs to integer types directly, as the input numbers may be too big to hold in primitive data types.
For example, AddStrings(“123”, “1”) = “124” and AddStrings(“99”, “2”) = “101”
When we add two numbers, we look at the 1’s position, and then carry over to 10’s etc. To convert a character ‘0’ to ‘9’ to its numerical value, we subtract 48 from its ASCII (48 is the ASCII code of ‘0’). Similarly, we add 48 to the integer 0 to 9 to get the string representation.
We use two index pointers, and at each iteration, we move the pointers and add the values respectively. If the pointer is over the length of the string, we simply add ZERO (you can add as many leading zeros to the number).
The C++ implementation below runs at complexity O(MAX(N, M)) where N and M are the string lengths of both input respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: string addStrings(string num1, string num2) { string r = ""; int sz1 = static_cast<int>(num1.size()); int sz2 = static_cast<int>(num2.size()); int i = 0, j = 0, c = 0; while (i < sz1 || j < sz2 || c > 0) { int t = c; t += i < sz1 ? num1[sz1 - i - 1] - 48 : 0; t += j < sz2 ? num2[sz2 - j - 1] - 48 : 0; r = string(1, t % 10 + 48) + r; c = t / 10; // carry over next digit i ++; j ++; } return r; } }; |
class Solution { public: string addStrings(string num1, string num2) { string r = ""; int sz1 = static_cast<int>(num1.size()); int sz2 = static_cast<int>(num2.size()); int i = 0, j = 0, c = 0; while (i < sz1 || j < sz2 || c > 0) { int t = c; t += i < sz1 ? num1[sz1 - i - 1] - 48 : 0; t += j < sz2 ? num2[sz2 - j - 1] - 48 : 0; r = string(1, t % 10 + 48) + r; c = t / 10; // carry over next digit i ++; j ++; } return r; } };
Adding two Strings in Python: Teaching Kids Programming – Add Two Big Integers in Strings
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: The Programmers Dont usually work over weekend
Next Post: How to Compute Shortest Distance to a Character in a String?
“we subtract it from 48 (which is the ASCII code of ‘0’)”
Don’t you mean ‘add it to 48’?
It is a bit confusing, post updated accordingly.
You can implement it without i, j and t you only need sz1, sz2 and t
yes, I know.