LeetCode problem#415

Add Strings

Solved in 1 languageJava

36 lines

1class Solution {
2    public String addStrings(String num1, String num2) {
3        StringBuilder sb = new StringBuilder();
4
5        int carry = 0;
6        for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry > 0; i--, j--)
7        {
8            int digit1;
9            int digit2;
10            if (i < 0)
11            {
12                digit1 = 0;
13            }
14            else
15            {
16                digit1 = num1.charAt(i) - '0';
17            }
18            if (j < 0)
19            {
20                digit2 = 0;
21            }
22            else
23            {
24                digit2 = num2.charAt(j) - '0';
25            }
26
27            int sum = digit1 + digit2 + carry;
28            carry = sum / 10;
29            sum = sum % 10;
30
31            sb.append(sum);
32        }
33
34        return sb.reverse().toString();
35    }
36}

How it works

The provided code is a solution for the LeetCode problem of adding two non-negative integers that are represented as strings (instead of numerical values). The problem arises because the values can be too large to fit into standard numerical types due to their length. Here's a breakdown of how the solution works:

Key Components:

StringBuilder: A StringBuilder is used to efficiently append the resulting digits of the sum.
Carry Handling: A variable carry is utilized to manage carrying over during the addition of digits when their sum exceeds 9.
Looping Through Digits: The loop processes the digits starting from the least significant to the most significant (from right to left). This is necessary because addition operates from the rightmost side (the unit place).

Detailed Explanation:

Setup:
- The solution begins by initializing a StringBuilder to store the result and a carry variable to handle any values that exceed a single digit during addition.
Loop:
- The for loop iterates as long as there are digits left in either num1 or num2 or there is a carry value greater than 0.
- The indices i and j start at the last digit of num1 and num2, respectively.
Fetching Digits:
- Inside the loop:
  - Each digit is extracted from the end of the respective strings.
  - If the index is out of bounds (less than 0), it assigns a digit value of 0, ensuring that we don't try to access a character that doesn't exist.
  - This is done using num1.charAt(i) - '0' to convert the character digit to its integer value.
Adding Digits:
- It computes the sum of the digits (digit1, digit2) from the two strings along with the carry.
- Then, it determines the new carry (if the sum is 10 or more) using integer division by 10 (carry = sum / 10).
- The value to append to the result is calculated using the modulo operation (sum % 10), which gives the rightmost digit of the sum.
Appending Result:
- The computed rightmost digit of the sum is appended to the StringBuilder. Since we are building the result from the least significant digit to the most significant, this results in the final string being in reverse order.
Final Output:
- After processing all digits and handling any remaining carry, the StringBuilder is reversed to arrange the digits in the correct order.
- Finally, the result is converted to a string and returned.

Complexity:

Time Complexity: O(max(len(num1), len(num2))), where len(num1) and len(num2) are the lengths of the input strings. This is because we may have to traverse both strings fully.
Space Complexity: O(n), where n is the length of the longer of the two input strings, for the result stored in StringBuilder.

Summary:

The code efficiently adds two numbers by manipulating their string representations, ensuring that it processes them digit-by-digit while managing the carry, just as one would do manually when adding numbers.

Written by AI from the code above, so double-check anything important.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.