Add Strings

Easy
0/40
profile
Contributed by
126 upvotes
Asked in companies
AppleFacebookAmazon

Problem statement

You are given two non-negative integers, ‘NUM1’ and ‘NUM2’, in the form of strings. Return the sum of both strings.


Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Example: 
Let ‘NUM1’ be: “5”
Let ‘NUM2’ be: “21”
The sum of both numbers will be: “26”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T’, denoting the number of test cases.

The first line of each test case contains two strings, ‘NUM1’ and ‘NUM2’, representing the two non-negative integers.
Output Format : 
For each test case, print the sum of both the strings.

Print the output of each test case in a separate line.
Constraints : 
1 <= T <= 10
1 <= |NUM1|, |NUM2| <= 10^5

NUM1 and NUM2 don’t have leading zeroes.
Where |NUM1| and |NUM2| denote the length of the respective strings.

Time limit: 1 sec
Sample Input 1 :
2
5 21
10 9
Sample output 1 :
26
19
Explanation For Sample Output 1 :
For the first test case:
The sum of both numbers will be: “26”.

For the second test case:
The sum of both numbers will be: “19”.
Sample Input 2 :
2
9 9
21 10
Sample output 2 :
18
31
Hint

Try to add the characters of the strings individually.

Approaches (1)
Brute-Force Approach

The basic idea is to add the character of the strings individually. We run a loop on both strings simultaneously from the end of the strings and add the sum of the characters. We also keep track of carry and update the result. If at any point sum of characters becomes greater than 9, we update the carry to 1.

 

Here is the algorithm:
 

  1. Create two variables (say, ‘IDX1’ and ‘IDX2’) to traverse the strings and initialize them with the length of the strings, respectively.
  2. Create a string (say, ‘RES’) to store the result.
  3. Create a variable (say, ‘CARRY’) to store the carry.
  4. Run a loop till ‘IDX1’ OR ‘IDX2’ is greater than or equal to 0.
    • Create a variable (say, ‘localSum’) to store the sum of the current characters and initialize it with 0.
    • Check if ‘IDX1’ is greater than or equal to 0.
      • Add the current character to ‘localSum’.
      • Decrease ‘IDX1’ by 0.
    • Similarly, check for ‘IDX2’ and add the current character.
    • Add the ‘CARRY’ to the ‘localSum’.
    • Check if ‘localSum’ is greater than 9.
      • Update ‘localSum’ by taking it mod with 10.
      • Update ‘CARRY’ with 1.
    • Add ‘localSum’ to the ‘RES’.
  5. Check if ‘CARRY’ is equal to 1.
    • Add ‘1’ to the ‘RES’.
  6. Reverse the string ‘RES’.
  7. Return ‘RES’.
Time Complexity

O(|NUM1| + |NUM2|), where |NUM1| and |NUM2| are the length of the strings.
 

We traverse both the strings once, which takes time equal to their lengths. Therefore, the overall time complexity will be O(|NUM1| + |NUM2|).

Space Complexity

O(1)

 

We don’t use any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Add Strings
Full screen
Console