43. Multiply Strings
Multiply Strings (LeetCode 43) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Multiply Strings (Manual Simulation) subpattern.
How to solve Multiply Strings
Multiply Strings is a Multiply Strings problem, part of String Manipulation Patterns. Learn to multiply large numbers represented as strings using manual simulation of multiplication.
Work towards the solution in these steps:
- Consider how you multiply numbers by hand digit by digit and how that process can be simulated with strings.
- Think about using an array to hold intermediate multiplication results to manage carries efficiently.
- Focus on how to map each digit multiplication to the correct position in the result array based on place value.
The reference solution runs in O(m * n) time and O(m + n) space.
The Multiply Strings solution and editorial walks through the full approach with reference code.
Problem statement
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input: num1 = "2", num2 = "3" Output: "6"
Example 2:
Input: num1 = "123", num2 = "456" Output: "56088"
Constraints:
- 1 <= num1.length, num2.length <= 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
Topics and companies
Topics: Math, String, Simulation.
Reported in interviews at Facebook, Microsoft, Amazon, Square, Apple, Bloomberg, Two Sigma, ByteDance.
How to practise Multiply Strings on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m + n) space.
Open Multiply Strings in the code editor, or read the Multiply Strings editorial for a worked solution with its approach and complexity analysis.
Where Multiply Strings sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Multiply Strings (Manual Simulation) subpattern
- The full DSA patterns sheet
Problems related to Multiply Strings
Other problems that use the same Multiply Strings (Manual Simulation) and String Manipulation Patterns techniques:
- Add Binary — Easy, same subpattern
- Add to Array-Form of Integer — Easy, same subpattern
- Plus One — Easy, same subpattern
- Concatenation of Array — Easy, same pattern
- Contains Duplicate — Easy, same pattern
- Design HashSet — Easy, same pattern
Multiply Strings FAQ
What is the LeetCode number of Multiply Strings?
Multiply Strings is LeetCode problem 43, rated Medium.
What pattern is used to solve Multiply Strings?
Multiply Strings is a Multiply Strings problem. It belongs to the String Manipulation Patterns pattern, in the Multiply Strings (Manual Simulation) subpattern.
What is the time complexity of Multiply Strings?
The reference solution runs in O(m * n) time and O(m + n) space.
Which companies ask Multiply Strings?
Multiply Strings has been reported in interviews at Facebook, Microsoft, Amazon, Square, Apple, Bloomberg, Two Sigma, ByteDance.