algoadvance

Leetcode 415. Add Strings

Problem Statement

Given two non-negative integers, num1 and num2 represented as strings, 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 in Java).
• You must also not convert the inputs to integers directly.

Clarifying Questions

1. Can the input strings contain leading zeros?
   • Yes, they might, but they should be treated as normal numbers (e.g., “0012” is the same as “12”).
2. What is the maximum length of the input strings?
   • The problem typically doesn’t state an exact maximum length, but you should write a solution that handles reasonably large sizes (up to several thousand digits).
3. Is it safe to assume that the input strings will always represent valid non-negative integers?
   • Yes, the input strings are always valid non-negative integers.

Strategy

1. Reverse Traversal: Start from the end of both strings and process each digit moving towards the beginning of the strings.
2. Addition with Carry: Initialize a carry variable to keep track of any carry-over during addition. For each digit, add the digits from the two strings (if present) and the carry.
3. Append Result: Append the resulting sum (digit-wise) to a StringBuilder and ensure you handle the carry after processing all digits.
4. Finalize Result: After processing all digits and accounting for any remaining carry, reverse the StringBuilder to get the final result.

Code

public class AddStrings {
    public String addStrings(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        
        while (i >= 0 || j >= 0 || carry > 0) {
            int digit1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int digit2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            result.append(sum % 10);
            
            i--;
            j--;
        }
        
        return result.reverse().toString();
    }

    public static void main(String[] args) {
        AddStrings solution = new AddStrings();
        System.out.println(solution.addStrings("123", "456")); // 579
        System.out.println(solution.addStrings("456", "77"));  // 533
        System.out.println(solution.addStrings("0", "0"));     // 0
    }
}

Time Complexity

• Time Complexity: (O(\max(N, M)))
  • Where (N) is the length of num1 and (M) is the length of num2. Each digit is processed once.
• Space Complexity: (O(\max(N, M)))
  • The size of the result will be at most one more digit than the longer input string, to account for any final carry.

This strategy ensures that we add the strings without converting them to integers directly, thus handling very large numbers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?