[Facebook] 415. Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

문자열로 표시된 두 개의 음이 아닌 정수 num1 및 num2가 주어지면 num1 및 num2의 합계를 반환합니다.

노트 :

num1 및 num2의 길이는 모두 <5100입니다.
num1과 num2는 모두 0-9의 숫자 만 포함합니다.
num1 및 num2 모두 선행 0을 포함하지 않습니다.
내장 BigInteger 라이브러리를 사용하거나 입력을 정수로 직접 변환해서는 안됩니다.

---

Overview

Facebook interviewers like this question and propose it in four main variations. The choice of algorithm should be based on the input format:

1. Strings (the current problem). Use schoolbook digit-by-digit addition. Note, that to fit into constant space is not possible for languages with immutable strings, for example, for Java and Python. Here are two examples:

   • Add Binary: sum two binary strings.

   • Add Strings: sum two non-negative numbers in a string representation without converting them to integers directly.

2. Integers. Usually, the interviewer would ask you to implement a sum without using + and - operators. Use bit manipulation approach. Here is an example:

   • Sum of Two Integers: Sum two integers without using + and - operators.

3. Arrays. The same textbook addition. Here is an example:

   • Add to Array Form of Integer.

4. Linked Lists. Sentinel Head + Textbook Addition. Here are some examples:

   • Plus One.

   • Add Two Numbers.

   • Add Two Numbers II.

개요

페이스 북 면접관은이 질문을 좋아하고 네 가지 주요 변형으로 제안합니다. 알고리즘 선택은 입력 형식을 기반으로해야합니다.

1. 문자열 (현재 문제). 교과서 자릿수 더하기를 사용하십시오. 예를 들어 Java 및 Python과 같이 변경 불가능한 문자열이있는 언어의 경우 상수 공간에 맞추는 것이 불가능합니다. 다음은 두 가지 예입니다.

* 이진 추가 : 두 이진 문자열을 더합니다.

* 문자열 추가 : 정수로 직접 변환하지 않고 문자열 표현에서 음이 아닌 두 수를 더합니다.

2. 정수. 일반적으로 면접관은 + 및-연산자를 사용하지 않고 합계를 구현하도록 요청합니다. 비트 조작 방식을 사용하십시오. 다음은 예입니다.

* 두 정수의 합계 : + 및-연산자를 사용하지 않고 두 정수를 더합니다.

 

3. 배열. 같은 교과서 추가. 다음은 그 예입니다.

* 정수 배열 형식에 추가합니다.

 

4. 연결된 목록. 센티넬 헤드 + 교과서 추가. 여기 몇 가지 예가 있어요.

* 하나 추가.

* 두 개의 숫자를 더합니다.

* 두 숫자 더하기 II.

---

Approach 1: Elementary Math

Here we have two strings as input and asked not to convert them to integers. Digit-by-digit addition is the only option here.

 

여기에 입력으로 두 개의 문자열이 있으며이를 정수로 변환하지 않도록 요청했습니다. 여기서 숫자 단위 추가는 유일한 옵션입니다.

 

 

1 / 6

Algorithm

• Initialize an empty res structure. Once could use array in Python and StringBuilder in Java.

• Start from carry = 0.

• Set a pointer at the end of each string: p1 = num1.length() - 1, p2 = num2.length() - 1.

• Loop over the strings from the end to the beginning using p1 and p2. Stop when both strings are used entirely.

  • Set x1 to be equal to a digit from string nums1 at index p1. If p1 has reached the beginning of nums1, set x1 to 0.

  • Do the same for x2. Set x2 to be equal to digit from string nums2 at index p2. If p2 has reached the beginning of nums2, set x2 to 0.

  • Compute the current value: value = (x1 + x2 + carry) % 10, and update the carry: carry = (x1 + x2 + carry) / 10.

  • Append the current value to the result: res.append(value).

• Now both strings are done. If the carry is still non-zero, update the result: res.append(carry).

• Reverse the result, convert it to a string, and return that string.

빈 res 구조를 초기화합니다. 한 번은 Python의 배열과 Java의 StringBuilder를 사용할 수 있습니다.

캐리 = 0에서 시작합니다.

각 문자열의 끝에 포인터를 설정하십시오. p1 = num1.length ()-1, p2 = num2.length ()-1.

p1 및 p2를 사용하여 끝에서 처음으로 문자열을 반복합니다. 두 문자열이 모두 사용되면 중지하십시오.

x1을 인덱스 p1에있는 문자열 nums1의 숫자와 같도록 설정합니다. p1이 nums1의 시작에 도달하면 se1은 0입니다.

x2에 대해서도 똑같이하십시오. x2를 인덱스 p2에있는 문자열 nums2의 숫자와 같도록 설정합니다. p2가 nums2의 시작 부분에 도달하면 x2를 0으로 설정합니다.

현재 값을 계산합니다 : value = (x1 + x2 + carry) % 10, carry를 업데이트합니다 : carry = (x1 + x2 + carry) / 10.

결과에 현재 값을 추가합니다 : res.append (value).

이제 두 문자열이 모두 완료되었습니다. 캐리가 여전히 0이 아니면 결과를 업데이트합니다 : res.append (carry).

결과를 반대로하고 문자열로 변환 한 다음 해당 문자열을 반환합니다.

 

 

Implementation

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder res = new StringBuilder();

        int carry = 0;
        int p1 = num1.length() - 1;
        int p2 = num2.length() - 1;
        while (p1 >= 0 || p2 >= 0) {
            int x1 = p1 >= 0 ? num1.charAt(p1) - '0' : 0;
            int x2 = p2 >= 0 ? num2.charAt(p2) - '0' : 0;
            int value = (x1 + x2 + carry) % 10;
            carry = (x1 + x2 + carry) / 10;
            res.append(value);
            p1--;
            p2--;    
        }
        
        if (carry != 0)
            res.append(carry);
        
        return res.reverse().toString();
    }
}

 

Complexity Analysis

• Time Complexity: \mathcal{O}(\max(N_1, N_2))O(max(N1​,N2​)), where N_1N1​ and N_2N2​ are length of nums1 and nums2. Here we do \max(N_1, N_2)max(N1​,N2​) iterations at most.

• Space Complexity: \mathcal{O}(\max(N_1, N_2))O(max(N1​,N2​)), because the length of the new string is at most \max(N_1, N_2) + 1max(N1​,N2​)+1.