Algorithm to Add Two Strings Numerically in C++


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) —

GD Star Rating
loading...
342 words
Last Post: The Programmers Dont usually work over weekend
Next Post: How to Compute Shortest Distance to a Character in a String?

The Permanent URL is: Algorithm to Add Two Strings Numerically in C++

4 Comments

  1. Jens Wienöbst

Leave a Reply