CODEWITHSUNDEEP
javastring
coderfromhell
coderfromhell

Reputation: 455

Multiply large string numbers without using Big-Integer library

I coded a simple solution which multiplied 2 integers given as strings and returned the product as a string. But it doesn't work for big values and I'm not allowed to use the Big-Integer library.

This is my current solution.

class Solution {
    public String multiply(String num1, String num2) {
        int numOne = 0;
        int numTwo = 0;
        
        for(char c : num1.toCharArray()){
            if((int)(c-'0') >= 0 && (int)(c-'0') <= 9){
                numOne = numOne*10 + (int)(c-'0');
            }
        }

        for(char c : num2.toCharArray()){
            if((int)(c-'0') >= 0 && (int)(c-'0') <= 9){
                numTwo = numTwo*10 + (int)(c-'0');
            }
        }
        
        return numOne*numTwo + "";
    }
}

I got an error in the following test case:

Input:
"123456789"
"987654321"
Output:
"-67153019"
Expected:
"121932631112635269"

What changes should I make so as to be able to multiply large numbers also?

Upvotes: 0

Views: 398

Answers (1)

cipher94
cipher94

Reputation: 203

For this, you can refer to the Karatsuba Multiplication algorithm.

You can do this too.

  1. If any of the numbers is negative pick up from substring 1 to n.
  2. Start from the last digit of second number.
  3. Multiply it with the first number. store the result.
  4. Do it with all the numbers of the second numbers and keep adding the result of the previous step to current step with ith shift in the position.

There are samples of this solution too on the internet. You will find it.

Upvotes: 3

Related Questions