Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = "11", num2 = "123" Output: "134"
Example 2:
Input: num1 = "456", num2 = "77" Output: "533"
Example 3:
Input: num1 = "0", num2 = "0" Output: "0"
Constraints:
1 <= num1.length, num2.length <= 104num1 and num2 consist of only digits.num1 and num2 don't have any leading zeros except for the zero itself.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.
The function addStrings adds two numbers represented as strings without converting them directly into integers. It accomplishes this by iterating over the digits in reverse, calculating the sum, and storing this in a result string. We keep the process efficient by using a simple loop to handle differing lengths of input strings, adding the carry and reversing the string at the end to present the final sum.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the maximum length of num1 or num2.
Space Complexity: O(n), for the result array.
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Reverse and Traverse | Time Complexity: |
| Character by Character Addition Using Two Pointers | Time Complexity: |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,125 views views
Watch 9 more video solutions →Practice Add Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor