Add Strings

Here’s a simple solution to add two given non-negative integers represented as strings without using any built-in library for handling large integers or converting the inputs to integers directly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j, carry, result = len(num1) - 1, len(num2) - 1, 0, []

        while i >= 0 or j >= 0 or carry:
            n1 = int(num1[i]) if i >= 0 else 0
            n2 = int(num2[j]) if j >= 0 else 0

            total = n1 + n2 + carry
            carry = total // 10

            result.append(str(total % 10))

            i -= 1
            j -= 1

        return ''.join(result[::-1])

This code iterates through the numbers from right to left, adding them digit by digit, and taking care of any carry from the previous step. If the numbers have different lengths, zeroes are used to fill in the shorter number. After completing the addition, the result is reversed and returned as a string.

Problem Definition

Define the Terms

Define the Interface

  Input: num1 (string), num2 (string)
  Output: string
Identify Implicit Inputs

Example: num1: ‘12’, num2: ‘13’ Example: num1: ‘12’, num2: ‘130’

Define the Goal

return the sum of num1 and num2

Identify the Constraints

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

Determine the Scope

  • List assumptions
  • Define boundaries of the problem

Search the Problem Space

  • Look for clues in the problem statement

Classify the Problem

  • Decontextualize the Problem

  • Can you think of this problem in a different way?

  • Can you reframe it?

Problem Representation

  • Analyze the Input and Output

  • Analyze the Examples

Solve the Problem by Hand

‘12’ ‘13’

‘12’ ‘130’

‘012’

Recognize the Pattern

Identify the Invariants

Brainstorm Solutions

  • Brute Force Approach

  • Shortcomings

  • Evaluate and Select Approach

Analyze Time and Space Complexity

  • Time: O( )
  • Space: O( )

Outline the Solution

Key Takeaways

Reflect

  • What went right?

  • What went wrong?

  • What can we improve next time?

1234

4321

123456

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# @param {String} num1
# @param {String} num2
# @return {String}
def add_strings(num1, num2)
  result = []
  carry = 0
  p1 = num1.size - 1
  p2 = num2.size - 1
  
  counter = [num1.size, num2.size].max + 1

  while p1 >= 0 || p2 >= 0
    x1 = p1 >= 0 ? num1[p1].ord - '0'.ord : 0
    x2 = p2 >= 0 ? num2[p2].ord - '0'.ord : 0

      add = (x1 + x2 + carry)
      value = add % 10
      result[counter] = value
      counter -= 1

      carry = add / 10
      p1 -= 1
      p2 -= 1
  end
    
  if carry != 0
      result[counter] = carry
  end
  
  result.join
end

Identifying Problem Isomorphism

“Add Strings” can be approximately mapped to the following problems:

  1. “Add Binary” (#67) on LeetCode
  2. “Multiply Strings” (#43) on LeetCode
  3. “Plus One” (#66) on LeetCode

Reasoning:

The problems share the common theme of dealing with numbers represented as strings and performing basic arithmetic operations on them.

  1. “Add Binary” is most directly isomorphic to “Add Strings” as both problems involve adding numbers represented as strings. However, “Add Binary” is slightly simpler because it only involves binary numbers (0 and 1), whereas “Add Strings” involves numbers from 0 to 9.

  2. “Multiply Strings” is a more complex problem than “Add Strings”. Both problems involve arithmetic operations on numbers represented as strings, but multiplication is generally considered a more complex operation than addition.

  3. “Plus One” can also be considered as a simpler isomorphic problem to “Add Strings”. In this problem, you have a digit array representing a non-negative integer and you need to increment the integer by one. It shares the concept of adding numbers with “Add Strings”, but it is simpler due to the fact that the addition operation is fixed to only adding one.

1
2
3
4
5
6
7
8

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        def str2int(num):
            result  = 0
            for n in num:
                result = result * 10 + ord(n) - ord('0')
            return result
        return str(str2int(num1) + str2int(num2))

Problem Classification

This problem can be classified into the following categories:

  1. Arithmetic and Number Theory: The problem is about performing addition operation on two numbers. Even though the numbers are represented as strings, the core problem is still about arithmetic.

  2. String Manipulation: The input numbers are given as strings and the result also needs to be a string. This adds an additional layer of complexity to the problem as one needs to perform the addition operation in a way that works with strings.

  3. Simulation: The problem can be seen as simulating the process of adding two numbers digit by digit from right to left, just like how we do it manually. This involves handling the carry from one digit to the next.

  4. Data Conversion: Although direct conversion of the entire string to an integer is not allowed, the problem involves converting individual characters to integers and vice versa.

Clarification Questions

What are the clarification questions we can ask about this problem?

Language Agnostic Coding Drills

To solve this problem, the main steps are as follows:

  1. String to Integer Conversion: This involves converting a string representation of a number to an integer. However, unlike the direct conversion allowed by most languages, the requirement here is to implement this manually. The conversion process involves starting from the most significant digit and progressing to the least significant digit, multiplying the current total by 10 and adding the current digit at each step.

    Drill: Write a function that takes a string representation of a non-negative integer and returns the integer. Use a loop to iterate through the characters of the string. Convert each character to its integer value, multiply the current total by 10 and add the current digit.

  2. Integer to String Conversion: After the addition, the result is an integer. This integer needs to be converted back to a string. This again needs to be done manually, similar to the previous step but in reverse order.

    Drill: Write a function that takes a non-negative integer and returns a string representation of the integer.

  3. String Addition: This step involves performing addition operation on the two integers that were converted from the input strings. This is relatively straightforward as it just requires using the ‘+’ operator. The result of this addition operation needs to be converted back to a string using the function from the previous step.

    Drill: Write a function that takes two string representations of non-negative integers, converts them to integers, performs addition operation, and returns the result as a string.

By doing these drills individually, one can master each of these smaller problems which can then be combined to solve the larger problem. This approach of breaking down a problem into smaller parts and practicing them individually is very effective for learning how to solve complex problems.

Targeted Drills in Python

  1. String to Integer Conversion Drill
1
2
3
4
5
6
7
8
9

def str_to_int(num_str: str) -> int:
    result = 0
    for ch in num_str:
        digit = ord(ch) - ord('0')  # Convert character to its corresponding integer value
        result = result * 10 + digit
    return result

# Testing the function
print(str_to_int('1234'))  # Should output: 1234
  1. Integer to String Conversion Drill
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def int_to_str(num: int) -> str:
    if num == 0:
        return '0'
    result = []
    while num > 0:
        num, digit = divmod(num, 10)
        result.append(chr(digit + ord('0')))  # Convert digit to its corresponding character value
    return ''.join(reversed(result))

# Testing the function
print(int_to_str(1234))  # Should output: '1234'
  1. String Addition Drill
1
2
3
4
5
6
7

def add_strings(num_str1: str, num_str2: str) -> str:
    num1 = str_to_int(num_str1)
    num2 = str_to_int(num_str2)
    return int_to_str(num1 + num2)

# Testing the function
print(add_strings('1234', '5678'))  # Should output: '6912'

Each of these drills tackles a specific subproblem - converting a string to an integer, converting an integer to a string, and adding two numbers represented as strings. Once these concepts are understood individually, they can be put together to solve the overall problem.