[leetcode #415] Add Strings

Problem

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 <= 10⁴
・ num1 and num2 consist of only digits.
・ num1 and num2 don't have any leading zeros except for the zero itself.

Idea

leetcode는 어려운 문제를 두 번 연속 내면 다음 문제는 꼭 쉬운 문제를 낸다. 주말동안 푼 두 문제는 고역이나 다름없었다면 오늘 문제는 힘든 두뇌를 잠시 쉬게 하는 느낌이었다. (그렇다고 내 풀이가 좋은 것은 아니다.)

문제에서는 build-in library를 쓰지 말라고 되어 있지만 길이가 최대 10,000이나 되는 숫자를 지원하는 library를 찾을 바에 그냥 숫자 하나씩 끝에서 더하는 편이 낫다. 우선 num1과 num2의 길이를 구한 뒤, 두 길이 중 더 큰 값을 기준으로 loop를 돌린다. 각 수의 가장 작은 자리 수부터 더하면 되고 올림은 따로 저장해 다음 iteration 때 활용하면 된다. 답을 낼 때 StringBuilder를 많이 사용할텐데, append한 뒤 reverse시키는 방법이 있지만 직관적으로 가장 앞자리에 insert해서 풀었다.

Solution

class Solution {
    public String addStrings(String num1, String num2) {
    	int m = num1.length();
    	int n = num2.length();
    	int resLength = Math.max(m, n);

    	int carry = 0;
    	int x = 0;
    	int y = 0;
    	int sum = 0;
    	StringBuilder s = new StringBuilder();
    	for (int i=0; i < resLength; i++) {
            if (m-i-1 >= 0)
            	x = num1.charAt(m-i-1) - '0';
            else
            	x = 0;

            if (n-i-1 >= 0)
            	y = num2.charAt(n-i-1) - '0';
            else
            	y = 0;

            sum = x + y + carry;
            carry = sum / 10;
            s.insert(0, sum % 10);
        }
        if (carry != 0)
            s.insert(0, carry);

        return s.toString();
    }
}

Reference

https://leetcode.com/problems/add-strings/