Katkat
Back

Add Two Arbitrarily Long Non-Negative Integers Given as Decimal Strings

MetaSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

Add two non-negative integers that are given as decimal digit strings, possibly thousands of digits long, and return the sum as a string without converting to built-in numbers. Tests digit-by-digit addition with carries, inputs of unequal length and canonical output without leading zeros.

You are given two non-negative integers written as strings of decimal digits. Return their sum, also written as a string of decimal digits.

The inputs can be thousands of digits long, far beyond any fixed-width integer type. Do not convert either input as a whole into a numeric type and do not use a big-integer library: the sum has to be produced from the digit strings themselves.

Function Signature

def add_decimal_strings(num1: str, num2: str) -> str:

Rules

  • Each input contains only the characters 0 through 9.
  • An input never has leading zeros, except the single-character string "0".
  • The two inputs may have different lengths.
  • The returned string must contain only decimal digits and have no leading zeros; a sum of zero is returned as "0".

Constraints

  • 1 <= len(num1) <= 10^4
  • 1 <= len(num2) <= 10^4
  • The represented values go far beyond 2^31 - 1 and 2^53, which is why whole-number conversion is ruled out; the answer is compared as a string, so checking it involves no numeric overflow.

Examples

Example 1

Input: num1 = "11", num2 = "123"
Output: "134"

Example 2

Input: num1 = "999", num2 = "1"
Output: "1000"

The final carry adds a new leading digit, so the result is longer than both inputs.

Example 3

Input: num1 = "0", num2 = "0"
Output: "0"