Interview Question - Biginteger Multiply Implementation

Question

Introducing Biginteger Multiply

• use an integer array to store biginteger as 297897654 will be stored as {2,9,7,8,9,7,6,5,4}
• implement the multiplication function for bigintegers
  Examples: {2, 9, 8, 8, 9, 8} * {3,6,3,4,5,8,9,9,2,2} = {1,0,8,6, 3,7,1, 4,1,8,7,8,9,7,6}

I was not able to implement this class and thought about it for several weeks without receiving an answer.

Can anyone help me implement it using C # / Java? Many thanks.

Answer 1

Do you know how to do multiplication on paper?

  123
x 456
-----
  738
 615
492
-----
56088

I would just implement this algorithm in code.

Answer 2

C ++ implementation:

Source:

#include <iostream>

using namespace std;

int main()
{
    int a[10] = {8,9,8,8,9,2};
    int b[10] = {2,1,9,8,5,4,3,6,3};

    // INPUT DISPLAY
    for(int i=9;i>=0;i--) cout << a[i];
    cout << " x ";
    for(int i=9;i>=0;i--) cout << b[i];
    cout << " = ";

    int c[20] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    for(int i=0;i<10;i++)
    {
            int carry = 0;
            for(int j=0;j<10;j++)
            {
                    int t = (a[j] * b[i]) + c[i+j] + carry;
                    carry = t/10;
                    c[i+j] = t%10;
            }
    }

    // RESULT DISPLAY
    for(int i=19;i>=0;i--) cout << c[i];
    cout << endl;
}

Conclusion:

0000298898 x 0363458912 = 00000108637141878976

Answer 3

, .
startegy. .
java.. ..

 package aoa;
    import java.io.*;
    public class LargeMult {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException
    {
        // TODO code application logic here
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter 1st number");
        String a=br.readLine();
        System.out.println("Enter 2nd number");
        String b=br.readLine();
        System.out.println("Result:"+multiply(a,b));

    }
    static String multiply(String t1,String t2)
    {

        if(t1.length()>1&&t2.length()>1)
        {
            int mid1=t1.length()/2;
            int mid2=t2.length()/2;
            String a=t1.substring(0, mid1);//Al
            String b=t1.substring(mid1, t1.length());//Ar
            String c=t2.substring(0, mid2);//Bl
            String d=t2.substring(mid2, t2.length());//Br
            String s1=multiply(a, c);
            String s2=multiply(a, d);
            String s3=multiply(b, c);
            String s4=multiply(b, d);


            long ans;
            ans=Long.parseLong(s1)*(long)Math.pow(10, 
            b.length()+d.length())+Long.parseLong(s3)*(long)Math.pow(10,d.length())+
            Long.parseLong(s2)*(long)Math.pow(10, b.length())+Long.parseLong(s4);
            return ans+"";
        }
        else

        {
            return (Integer.parseInt(t1)*Integer.parseInt(t2))+"";
        }   
    }
}    

, ! ..

Answer 4

Python :

def mul(one,two):
    return map(int,str(int("".join(map(str,one))) * int("".join(map(str,two)))))

:

>>> mul([2,7,6],[1,0,5])
[2, 8, 9, 8, 0]

Answer 5

, Add(), . , . , Add(), Multipy() .

public static int[] Add(int[] a, int[] b) {
   var maxLen = (a.Length > b.Length ? a.Length : b.Length);
   var carryOver = 0;
   var result = new List<int>();
   for (int i = 0; i < maxLen; i++) {
      var idx1 = a.Length - i - 1;
      var idx2 = b.Length - i - 1;
      var val1 = (idx1 < 0 ? 0 : a[idx1]);
      var val2 = (idx2 < 0 ? 0 : b[idx2]);

      var addResult = (val1 + val2) + carryOver;
      var strAddResult = String.Format("{0:00}", addResult);
      carryOver = Convert.ToInt32(strAddResult.Substring(0, 1));
      var partialAddResult = Convert.ToInt32(strAddResult.Substring(1));
      result.Insert(0, partialAddResult);
   }
   if (carryOver > 0) result.Insert(0, carryOver);
   return result.ToArray();
}

Answer 6

Hint: use divide-and-conquer to split the int into halves, this can effectively reduce the time complexity from O (n ^ 2) to O (n ^ (log3)). The bottom line is to reduce multiplication operations.

Answer 7

I am posting the java code I wrote. Hope this helps

import org.junit.Test;
import static org.junit.Assert.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
* Created by ${YogenRai} on 11/27/2015.
*
* method multiply BigInteger stored as digits in integer array and returns results
*/
public class BigIntegerMultiply {
   public static List<Integer> multiply(int[] num1,int[] num2){
    BigInteger first=new BigInteger(toString(num1));
    BigInteger result=new BigInteger("0");
    for (int i = num2.length-1,k=1; i >=0; i--,k=k*10) {
        result =  (first.multiply(BigInteger.valueOf(num2[i]))).multiply(BigInteger.valueOf(k)).add(result);
    }
    return convertToArray(result);
}

private static List<Integer> convertToArray(BigInteger result) {
    List<Integer> rs=new ArrayList<>();
    while (result.intValue()!=0){
        int digit=result.mod(BigInteger.TEN).intValue();
        rs.add(digit);
        result = result.divide(BigInteger.TEN);
    }
    Collections.reverse(rs);
    return rs;
}

public static String toString(int[] array){
    StringBuilder sb=new StringBuilder();
    for (int element:array){
        sb.append(element);
    }
    return sb.toString();
}

@Test
public void testArray(){
    int[] num1={2, 9, 8, 8, 9, 8};
    int[] num2 = {3,6,3,4,5,8,9,1,2};
    System.out.println(multiply(num1, num2));
}

}