Katkat
Back

Add two integer strings using digit-adder

Two SigmaData Scientist · Technical Screen
HardData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests string manipulation, modular arithmetic, and the ability to manage carry-over logic manually to perform addition on integers that exceed the capacity of standard numeric data types.

Problem Statement

Given two non-negative integers represented as strings num1 and num2, return the sum of the two integers as a string. You must implement the addition manually without converting the entire input strings to native integer types (e.g., you cannot use int(num1) + int(num2)).

Constraints

  • The lengths of num1 and num2 are between 1 and 10,000.
  • num1 and num2 consist of digits '0'-'9'.
  • num1 and num2 do not contain any leading zeros except for the number "0" itself.

Function Signature

def add_strings(num1: str, num2: str) -> str:
    pass

Examples

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

Example 2: Input: num1 = "456", num2 = "77" Output: "533" Explanation: 6+7=13 (write 3, carry 1), 5+7+1=13 (write 3, carry 1), 4+1=5.

Edge Cases

  • One string is significantly longer than the other.
  • The sum results in an extra digit (e.g., "99" + "1" = "100").
  • Both inputs are "0".

Hints

Hint 1

Initialize two pointers at the end of each string and move backwards towards the beginning.

Hint 2

Use a variable to keep track of the carry that results from adding digits whose sum is 10 or greater.

Hint 3

If one string is exhausted before the other, treat the remaining digits of the longer string as if they are being added to 0.

Follow-up questions

  • How would you modify your solution to support negative numbers represented as strings?
  • Could this algorithm be parallelized if the strings were millions of characters long?
  • How would you adapt this logic to perform multiplication instead of addition?