Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/415.html

415. Add Strings (Easy)

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.

Companies:
Facebook, Microsoft

Related Topics:
Math

Similar Questions:

Solution 1.

  • class Solution {
        public String addStrings(String num1, String num2) {
            if (num1.equals("0") && num2.equals("0"))
                return "0";
            int length1 = num1.length(), length2 = num2.length();
            while (num1.length() < length2)
                num1 = "0" + num1;
            while (num2.length() < length1)
                num2 = "0" + num2;
            int totalLength = Math.max(length1, length2) + 1;
            int[] sumArray = new int[totalLength];
            for (int i = totalLength - 1; i > 0; i--) {
                int digit1 = num1.charAt(i - 1) - '0';
                int digit2 = num2.charAt(i - 1) - '0';
                sumArray[i] += digit1 + digit2;
                if (sumArray[i] >= 10) {
                    sumArray[i - 1] += sumArray[i] / 10;
                    sumArray[i] %= 10;
                }
            }
            StringBuffer sb = new StringBuffer();
            if (sumArray[0] != 0)
                sb.append(sumArray[0]);
            for (int i = 1; i < totalLength; i++)
                sb.append(sumArray[i]);
            String sum = sb.toString();
            return sum;
        }
    }
    
    ############
    
    class Solution {
        public String addStrings(String num1, String num2) {
            int i = num1.length() - 1, j = num2.length() - 1;
            StringBuilder ans = new StringBuilder();
            for (int c = 0; i >= 0 || j >= 0 || c > 0; --i, --j) {
                int a = i < 0 ? 0 : num1.charAt(i) - '0';
                int b = j < 0 ? 0 : num2.charAt(j) - '0';
                c += a + b;
                ans.append(c % 10);
                c /= 10;
            }
            return ans.reverse().toString();
        }
    
        public String subStrings(String num1, String num2) {
            int m = num1.length(), n = num2.length();
            boolean neg = m < n || (m == n && num1.compareTo(num2) < 0);
            if (neg) {
                String t = num1;
                num1 = num2;
                num2 = t;
            }
            int i = num1.length() - 1, j = num2.length() - 1;
            StringBuilder ans = new StringBuilder();
            for (int c = 0; i >= 0; --i, --j) {
                c = (num1.charAt(i) - '0') - c - (j < 0 ? 0 : num2.charAt(j) - '0');
                ans.append((c + 10) % 10);
                c = c < 0 ? 1 : 0;
            }
            while (ans.length() > 1 && ans.charAt(ans.length() - 1) == '0') {
                ans.deleteCharAt(ans.length() - 1);
            }
            if (neg) {
                ans.append('-');
            }
            return ans.reverse().toString();
        }
    }
    
  • // OJ: https://leetcode.com/problems/add-strings/
    // Time: O(M + N)
    // Space: O(1)
    class Solution {
    public:
        string addStrings(string a, string b) {
            string sum;
            int carry = 0;
            auto i = a.rbegin(), j = b.rbegin();
            while (i != a.rend() || j != b.rend() || carry) {
                if (i != a.rend()) carry += *i++ - '0';
                if (j != b.rend()) carry += *j++ - '0';
                sum += (carry % 10) + '0';
                carry /= 10;
            }
            reverse(sum.begin(), sum.end());
            return sum;
        }
    };
    
  • class Solution:
        def addStrings(self, num1: str, num2: str) -> str:
            i, j = len(num1) - 1, len(num2) - 1
            ans = []
            c = 0
            while i >= 0 or j >= 0 or c:
                a = 0 if i < 0 else int(num1[i])
                b = 0 if j < 0 else int(num2[j])
                c, v = divmod(a + b + c, 10) # nice
                ans.append(str(v))
                i, j = i - 1, j - 1
            return "".join(ans[::-1])
    
        # follow-up, substract
        def subStrings(self, num1: str, num2: str) -> str:
            m, n = len(num1), len(num2)
            neg = m < n or (m == n and num1 < num2)
            if neg:
                num1, num2 = num2, num1
            i, j = len(num1) - 1, len(num2) - 1
            ans = []
            c = 0
            while i >= 0:
                c = int(num1[i]) - c - (0 if j < 0 else int(num2[j]))
                ans.append(str((c + 10) % 10))
                c = 1 if c < 0 else 0
                i, j = i - 1, j - 1
            
            # eg. 99199 - 99198 = 1, ans here is "10000"
            while len(ans) > 1 and ans[-1] == "0":
                ans.pop()
            if neg: # will not be "-0", neg only when <0
                ans.append("-")
            return "".join(ans[::-1])
    
    ############
    
    class Solution(object):
      def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        carry = 0
        i = len(num1) - 1
        j = len(num2) - 1
        ans = ""
        for k in reversed(range(0, max(len(num1), len(num2)))):
          a = int(num1[i]) if i >= 0 else 0
          b = int(num2[j]) if j >= 0 else 0
          i, j = i - 1, j - 1
          c = carry
          carry = 0
          sum = a + b + c
          if sum >= 10:
            carry = 1
            ans += str(sum - 10)
          else:
            ans += str(sum)
        if carry == 1:
          ans += "1"
        return ans[::-1]
    
    
  • func addStrings(num1 string, num2 string) string {
    	i, j := len(num1)-1, len(num2)-1
    	ans := []byte{}
    	for c := 0; i >= 0 || j >= 0 || c > 0; i, j = i-1, j-1 {
    		if i >= 0 {
    			c += int(num1[i] - '0')
    		}
    		if j >= 0 {
    			c += int(num2[j] - '0')
    		}
    		ans = append(ans, byte(c%10+'0'))
    		c /= 10
    	}
    	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    		ans[i], ans[j] = ans[j], ans[i]
    	}
    	return string(ans)
    }
    
    func subStrings(num1 string, num2 string) string {
    	m, n := len(num1), len(num2)
    	neg := m < n || (m == n && num1 < num2)
    	if neg {
    		num1, num2 = num2, num1
    	}
    	i, j := len(num1)-1, len(num2)-1
    	ans := []byte{}
    	for c := 0; i >= 0; i, j = i-1, j-1 {
    		c = int(num1[i]-'0') - c
    		if j >= 0 {
    			c -= int(num2[j] - '0')
    		}
    		ans = append(ans, byte((c+10)%10+'0'))
    		if c < 0 {
    			c = 1
    		} else {
    			c = 0
    		}
    	}
    	for len(ans) > 1 && ans[len(ans)-1] == '0' {
    		ans = ans[:len(ans)-1]
    	}
    	if neg {
    		ans = append(ans, '-')
    	}
    	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    		ans[i], ans[j] = ans[j], ans[i]
    	}
    	return string(ans)
    }
    
  • function addStrings(num1: string, num2: string): string {
        const res = [];
        let i = num1.length - 1;
        let j = num2.length - 1;
        let isOver = false;
        while (i >= 0 || j >= 0 || isOver) {
            const x = Number(num1[i--]) || 0;
            const y = Number(num2[j--]) || 0;
            const sum = x + y + (isOver ? 1 : 0);
            isOver = sum >= 10;
            res.push(sum % 10);
        }
        return res.reverse().join('');
    }
    
    
  • /**
     * @param {string} num1
     * @param {string} num2
     * @return {string}
     */
    var addStrings = function (num1, num2) {
        let i = num1.length - 1;
        let j = num2.length - 1;
        const ans = [];
        for (let c = 0; i >= 0 || j >= 0 || c; --i, --j) {
            c += i < 0 ? 0 : parseInt(num1.charAt(i), 10);
            c += j < 0 ? 0 : parseInt(num2.charAt(j), 10);
            ans.push(c % 10);
            c = Math.floor(c / 10);
        }
        return ans.reverse().join('');
    };
    
    /**
     * @param {string} num1
     * @param {string} num2
     * @return {string}
     */
    var subStrings = function (num1, num2) {
        const m = num1.length;
        const n = num2.length;
        const neg = m < n || (m == n && num1 < num2);
        if (neg) {
            const t = num1;
            num1 = num2;
            num2 = t;
        }
        let i = num1.length - 1;
        let j = num2.length - 1;
        const ans = [];
        for (let c = 0; i >= 0; --i, --j) {
            c = parseInt(num1.charAt(i), 10) - c;
            if (j >= 0) {
                c -= parseInt(num2.charAt(j), 10);
            }
            ans.push((c + 10) % 10);
            c = c < 0 ? 1 : 0;
        }
        while (ans.length > 1 && ans[ans.length - 1] == '0') {
            ans.pop();
        }
        if (neg) {
            ans.push('-');
        }
        return ans.reverse().join('');
    };
    
    
  • impl Solution {
        pub fn add_strings(num1: String, num2: String) -> String {
            let mut res = vec![];
            let s1 = num1.as_bytes();
            let s2 = num2.as_bytes();
            let (mut i, mut j) = (s1.len(), s2.len());
            let mut is_over = false;
            while i != 0 || j != 0 || is_over {
                let mut sum = if is_over { 1 } else { 0 };
                if i != 0 {
                    sum += (s1[i - 1] - b'0') as i32;
                    i -= 1;
                }
                if j != 0 {
                    sum += (s2[j - 1] - b'0') as i32;
                    j -= 1;
                }
                is_over = sum >= 10;
                res.push((sum % 10).to_string());
            }
            res.into_iter().rev().collect()
        }
    }
    
    

All Problems

All Solutions