Multiply Strings - InterviewBit Solution

Problem: Multiply Strings

Problem Description:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative. Note2: Your answer should not have leading zeroes. For example, 00 is not a valid answer.

For example,

Given strings "12", "10", your answer should be “120”.

NOTE: DO NOT USE BIG INTEGER LIBRARIES ( WHICH ARE AVAILABLE IN JAVA / PYTHON ). We will retroactively disqualify such submissions and the submissions will incur penalties.

Solution Approach:

Doing it without using Big Integer Libraries is quite tiresome, but anyways let's do it:)

The approach to solve this is the same as how we solve it on paper. But since it is a program, we can write it more elegantly, as we know we have to add the multiplication in the end, so instead of doing it in end, we can keep doing that addition while multiplying as well. Since this will be done by the processor so we don't have to worry about the complexity of operations/calculations, we just have to worry about the complexity of the Algorithm :D

Time Complexity: O(N*M)

Where N is the length of string A, and M is the length of string B.

Space Complexity O(N+M)

Solution:

Code in C++