Sponsored
Sponsored
This approach involves reversing both input strings, then iterating through them to sum up each digit, similar to manual addition from the rightmost digit. This technique simplifies handling the carry over during addition.
Time Complexity: O(n), where n is the maximum length of num1 or num2.
Space Complexity: O(n), for the result array.
1#include <iostream>
2#include <string>
3using namespace std;
4
5string addStrings(string num1, string num2) {
6 string result = "";
7 int carry = 0, i = num1.size() - 1, j = num2.size() - 1;
8
9 while (i >= 0 || j >= 0 || carry) {
10 int sum = carry;
11 if (i >= 0) sum += num1[i--] - '0';
12 if (j >= 0) sum += num2[j--] - '0';
13
14 result += (sum % 10) + '0';
15 carry = sum / 10;
16 }
17
18 reverse(result.begin(), result.end());
19 return result;
20}
21
22int main() {
23 string num1 = "11", num2 = "123";
24 cout << addStrings(num1, num2) << endl;
25 return 0;
26}This solution follows a similar logic to the C solution, iterating through the digits in reverse order from the two input strings. After computing the sum and carry for each pair of digits, we reverse the result string to complete the addition. The use of C++'s string class simplifies string operations, such as concatenation and reversing.
This approach deploys two pointers, initially positioned at the end of each input string. We process each character one by one, moving the pointers from the rightmost end towards the start of each string. This allows us to readily manage the carry as we compute the sum step-by-step.
Time Complexity: O(n), where n is the maximum length of num1 or num2.
Space Complexity: O(n), necessary for the dynamically allocated result string.
1
This C implementation utilizes dynamic memory allocation to handle the expected length of the result string. By manipulating pointers, the implementation skillfully confines carry operations within the loop. The function returns a pointer to the correct start of the result string after adjusting for any leading zeros produced by initial carry operations.