Problem 43

Abstract / Summary

Given two numbers as strings multiply them and return the result as a string without using built in conversion functions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 0043.cpp

class Solution {
public:
    void addReversed(string& result, string& num2)
    {
        while (result.size() < num2.size() && num2.back() == '0')
            num2.pop_back();
        while (result.size() < num2.size())
            result += '0';
        while (result.size() > num2.size())
            num2 += '0';

        int carry = 0;
        for (int i = 0; i < result.size(); i++)
        {
            auto sum = carry + (result[i] - '0') + (num2[i] - '0');
            result[i] = (sum % 10) + '0';
            carry = sum / 10;
        }
        if (carry > 0)
            result += '1';
    }

    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";

        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        // premultiplied
        string two[10];
        string singleSum = num2;
        for (int i = 1; i <= 9; i++)
        {
            two[i] = singleSum;
            addReversed(singleSum, num2);
        }

        string result;
        for (auto one : num1)
        {
            int factor = one - '0';
            addReversed(result, two[factor]);

            for (auto& t : two)
                t.insert(t.begin(), '0');
        }

        reverse(result.begin(), result.end());
        return result;
    }
};

52 lines | 1384 bytes | submitted August 7, 2023 | GitHub   2% comment ratio | tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 45% (2+ million submissions).

Typical patterns to solve this problem:
  • Math
  • Simulation
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class that multiplies two non-negative integer values represented as decimal strings. The algorithm works entirely with character arrays, avoiding conversion to built-in numeric types, which allows it to handle arbitrarily large numbers. The multiplication proceeds by reversing the input strings, precomputing scaled versions of the second operand, and repeatedly adding these scaled strings to an accumulating result.

Core Functions

addReversed

addReversed adds the contents of num2 to result assuming both strings are stored in reverse order (least significant digit first). The function first discards any trailing zeros in num2 that would not affect the sum when result is shorter. It then equalizes the lengths of the two strings by appending '0' characters to the shorter one. The core addition loop iterates over each digit, computes the sum with a carry, writes the new digit back into result, and updates the carry. If a carry remains after processing all positions, an extra '1' is appended.

void addReversed(string& result, string& num2)
{
    while (result.size() < num2.size() && num2.back() == '0')
        num2.pop_back();
    while (result.size() < num2.size())
        result += '0';
    while (result.size() > num2.size())
        num2 += '0';

    int carry = 0;
    for (int i = 0; i < result.size(); i++)
    {
        auto sum = carry + (result[i] - '0') + (num2[i] - '0');
        result[i] = (sum % 10) + '0';
        carry = sum / 10;
    }
    if (carry > 0)
        result += '1';
}

multiply

multiply orchestrates the overall multiplication. It begins with a quick check for either operand being "0" and returns "0" immediately, handling the trivial zero case. Both input strings are reversed to align least significant digits at index 0, simplifying digit-wise operations.

A pre-multiplication table two[10] is built where two[i] holds the product of num2 with the digit i. Starting from i = 1, each entry is generated by repeatedly invoking addReversed on a running sum singleSum. This creates all necessary scaled versions of num2 without recomputing them from scratch for each digit of num1.

The main accumulation loop iterates over each character one in the reversed num1. The numeric value of one selects the appropriate pre-scaled string two[factor], which is then added to result via addReversed. After each addition, every entry in the pre-scaled table is shifted left by inserting a '0' at the front, effectively multiplying each entry by ten to align with the next higher digit position of num1.

Finally, the accumulated result string, still in reverse order, is reversed back to normal orientation before being returned.

string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0")
        return "0";

    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());

    // premultiplied
    string two[10];
    string singleSum = num2;
    for (int i = 1; i <= 9; i++)
    {
        two[i] = singleSum;
        addReversed(singleSum, num2);
    }

    string result;
    for (auto one : num1)
    {
        int factor = one - '0';
        addReversed(result, two[factor]);

        for (auto& t : two)
            t.insert(t.begin(), '0');
    }

    reverse(result.begin(), result.end());
    return result;
}

Edge Cases Handled

The implementation explicitly checks for the presence of a zero operand at the very start of multiply. By returning "0" immediately, it avoids unnecessary processing and guarantees correct output for inputs like "0" paired with any other numeric string.

Within addReversed, the loop that removes trailing '0' characters from num2 when result is shorter ensures that superfluous zeros do not inflate the length of the operand, preventing incorrect carry propagation. The length-balancing steps guarantee that both strings have identical sizes before digit-wise addition, which eliminates out-of-range accesses.

The pre-multiplication table is built only for digits 1 through 9. The entry for 0 remains empty, and when a digit of num1 is '0', the addition step effectively adds an empty string, leaving the accumulated result unchanged. This behavior correctly models the contribution of a zero multiplier digit.

The final reversal of result restores the conventional most-significant-digit-first representation, ensuring that the returned string does not contain leading zeros (except the single zero case handled earlier).

Performance Optimizations

The code avoids repeated multiplication of num2 by each digit of num1 by constructing a lookup table two[10] that stores all possible single-digit products of num2. This precomputation reduces the number of addition operations required during the main loop, as each digit of num1 can be processed with a single addReversed call.

addReversed performs in-place updates on the result string, eliminating the need for auxiliary buffers or temporary copies. By appending zeros to the shorter operand rather than creating new padded strings, the function minimizes memory allocations.

The shifting of all pre-scaled strings after each digit of num1 is achieved by inserting a '0' at the beginning of each string. This operation is cheap because the strings are stored in reverse order; inserting at the front corresponds to appending a zero to the least significant side of the actual number, which aligns naturally with the reversed representation.

Overall, the algorithm leverages digit-wise addition, precomputed multiples, and in-place string manipulation to achieve an efficient multiplication routine for large integer strings without resorting to heavyweight big-integer libraries.

written by openai gpt

ELI5 - Simplified Explanation

Imagine there are two large numbers made of blocks. Because they are too big for a normal box, they are saved as a row of letters. Since computers find it easier to work from the back to the front, the code begins by flipping these rows around.

The task is to multiply these numbers, which is like stacking sets of blocks repeatedly. The code prepares a special shelf of pre-stacked blocks for the numbers one through nine. To get these stacks, it uses a helper tool that adds numbers together. Adding is handled by looking at each pair of blocks and keeping track of when a set of ten is finished, which is passed over as a little bonus to the next spot.

When multiplying, the code looks at each digit in the first number. It grabs the matching stack from the shelf and adds it to an overall pile. Before moving to the next digit, the code adds an extra empty block to the front of all the stacks on the shelf. This acts just like when humans write down a zero while working out math problems on paper to keep everything in the right place.

After all the digits have been processed and added to the big pile, the final result is currently facing the wrong way. The code flips the result one last time to make the number readable in the correct order.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 28 | median = 4.5 | μ = 4.61 | σ = 1.80

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python Rust JS C# Go PHP TS
LeetcodeHelp C++ Java Python
MemoryLimitExceeded C++ Python
Progiez C++ Java Python
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
fartem Ruby
fengvyi C++
fpdjsns C++
gaosq0604 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
fartem Ruby
fengvyi C++
fpdjsns C++
gaosq0604 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
MacJim C++
qiyuangong Python
ruoru Rust
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
53 links | 35 authors | 12 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Multiply Strings - Leetcode 43 - Python'
NeetCode 18 mins
Multiply Strings - Leetcode 43 - Python
YouTube video 'Multiply Strings | Leetcode 43 Solution in Hindi'
Pepcoding 50 mins
Multiply Strings | Leetcode 43 Solution in Hindi
YouTube video 'Multiply Strings || Leetcode 43 || C++ Solution'
Unnati Mishra 7 mins
Multiply Strings || Leetcode 43 || C++ Solution
YouTube video 'LeetCode 43. Multiply Strings Explantion and Solution'
happygirlzt 11 mins
LeetCode 43. Multiply Strings Explantion and Solution
YouTube video 'Multiply Strings | Leetcode 43 | Live coding session 🔥🔥🔥'
Coding Decoded 10 mins
Multiply Strings | Leetcode 43 | Live coding session 🔥🔥🔥
YouTube video 'LeetCode 43. Multiply Strings 中文解释 Chinese Version'
happygirlzt 12 mins
LeetCode 43. Multiply Strings 中文解释 Chinese Version
YouTube video 'LeetCode 43 | Multiply Strings | Math | Java'
Sleepy Cracker 9 mins
LeetCode 43 | Multiply Strings | Math | Java
YouTube video 'Multiply Strings Python Solution - LeetCode #43'
Professor Oakes 7 mins
Multiply Strings Python Solution - LeetCode #43
YouTube video 'Leetcode Question 43 "Multiply Strings" in Javascript'
Ghumman Tech 7 mins
Leetcode Question 43 "Multiply Strings" in Javascript
YouTube video '167. Leetcode 43. Multiply Strings : JAVA'
Web Fusion with Bharadwaj 16 mins
167. Leetcode 43. Multiply Strings : JAVA
YouTube video 'Multiply Strings - LeetCode #43 - C++'
Sean Chuah 11 mins
Multiply Strings - LeetCode #43 - C++
YouTube video 'LeetCode: 43. Multiply Strings (Visualized)'
Code With Zi 16 mins
LeetCode: 43. Multiply Strings (Visualized)
YouTube video 'Daily Leetcode #586: Nov 07, 2021 - 43. Multiply Strings'
Programming Live with Larry 17 mins
Daily Leetcode #586: Nov 07, 2021 - 43. Multiply Strings
YouTube video 'Microsoft Coding Interview Question | Leetcode 43 | Multiply Strings'
WorkWithGoogler 7 mins
Microsoft Coding Interview Question | Leetcode 43 | Multiply Strings
YouTube video 'LeetCode #43 (Multiply Strings) using Python | Solving all 150 NeetCode Problems | Episode 32'
CodeMeetsWorld 23 mins
LeetCode #43 (Multiply Strings) using Python | Solving all 150 NeetCode Problems | Episode 32
YouTube video 'Leetcode 43: Multiply Strings in Telugu | Brute Force, Paper Method, Python DSA | srkcodes'
Srk Codes 20 mins
Leetcode 43: Multiply Strings in Telugu | Brute Force, Paper Method, Python DSA | srkcodes
YouTube video 'LeetCode in C# | 43. Multiply Strings'
Josh Ackland 11 mins
LeetCode in C# | 43. Multiply Strings
YouTube video '140. Leetcode 43. Multiply Strings : Javascript'
Web Fusion with Bharadwaj 18 mins
140. Leetcode 43. Multiply Strings : Javascript
YouTube video 'Day 348: LeetCode Problem 43. Multiply Strings - Swift'
iOSxBank 11 mins
Day 348: LeetCode Problem 43. Multiply Strings - Swift
YouTube video 'Amazon Software Engineer Interview Preparation - Part 31 LC 43 Multiply Strings'
Ghumman Tech 12 mins
Amazon Software Engineer Interview Preparation - Part 31 LC 43 Multiply Strings
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

40 easy 30 medium 1 hard
72 solutions   August 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality