Java O(n) Easy To Understand, Optimal Solution


  • 1
    B

    Explanation
    The idea to this question is to approach it the same way we are performing addition on paper. We start from the right-most indices of both num1, num2, and add up digits in-sync, while remembering to carry the 1 when necessary.

    Time Complexity
    The time complexity is O(n) where n is the max(# chars in num1, # chars in num2), since we iterate through both num1, num2 until they both run out of characters.

    class Solution {
        public String addStrings(String num1, String num2) {
            StringBuilder sb = new StringBuilder();
            int index1 = num1.length() - 1;
            int index2 = num2.length() - 1;
            int carry = 0;
            
            while (index1 >= 0 || index2 >= 0 || carry == 1) {
                // If possible, we use values at indices 
                int val1 = (index1 >= 0) ? 
                           (int) num1.charAt(index1) - '0' : 0;
                int val2 = (index2 >= 0) ?
                           (int) num2.charAt(index2) - '0' : 0;
    
                // Resulting sum
                int sum = val1 + val2 + carry;
    
                // Compute carry, digit to insert
                carry = sum / 10;
                int digit = sum % 10;
    
                // Insert at the beginning of our sb
                sb.insert(0, (char) (digit + '0'));
                index1--; index2--;
            }
            return new String(sb);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.