Goldman Sachs Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
You can implement Karatsuba algorithm for large number multiplication.
Please see the code below for the same.
import java.util.Scanner;
/**
* The Class LargeMultiplication.
*
* @author Bhavik Ambani
*/
public class LargeMultiplication {
/**
* Function to multiply two numbers *.
*
* @param x
* the x
* @param y
* the y
* @return the long
*/
public long multiply(long x, long y) {
int size1 = getSize(x);
int size2 = getSize(y);
/** Maximum of lengths of number **/
int N = Math.max(size1, size2);
/** for small values directly multiply **/
if (N < 10)
return x * y;
/** max length divided, rounded up **/
N = (N / 2) + (N % 2);
/** multiplier **/
long m = (long) Math.pow(10, N);
/** compute sub expressions **/
long b = x / m;
long a = x - (b * m);
long d = y / m;
long c = y - (d * N);
/** compute sub expressions **/
long z0 = multiply(a, c);
long z1 = multiply(a + b, c + d);
long z2 = multiply(b, d);
return z0 + ((z1 - z0 - z2) * m) + (z2 * (long) (Math.pow(10, 2 * N)));
}
/**
* Gets the size.
*
* @param num
* the num
* @return the size
*/
public int getSize(long num) {
int ctr = 0;
while (num != 0) {
ctr++;
num /= 10;
}
return ctr;
}
/**
* Main function *.
*
* @param args
* the arguments
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("LargeMultiplication Algorithm Test\n");
LargeMultiplication kts = new LargeMultiplication();
/** Accept two integers **/
System.out.println("Enter two integer numbers\n");
long n1 = scan.nextLong();
long n2 = scan.nextLong();
scan.close();
/** Call function multiply of class Karatsuba **/
long product = kts.multiply(n1, n2);
System.out.println("\nProduct : " + product);
}
}
public static void main(String[] args) {
int[] a = { 5,3,6,2,8,2,0,2,8 };
int[] b = { 3,5,2,3,2,1,3,4 };
int[] c = new int[a.length + b.length];
int k = c.length - 1;
int carry = 0;
for (int i = a.length -1; i >= 0; i--) {
int temp = k-(a.length-i-1);
int count = 0;
for (int j = b.length-1; j >= 0; j--) {
int sum = a[i]*b[j]+ c[temp-count]+carry;
int value = sum % 10;
c[temp-count] = value;
carry = sum/10;
count++;
}
c[temp-count] = carry;
carry = 0;
}
System.out.println(Arrays.toString(c));
}
public class LargeMultiplication
- Pradeep kumar R S January 15, 2015{
public static void main( String[] args )
{
int[] Num1 = { 5,3,6,2,8,2,0,2,8 };
int[] Num2 = { 3,5,2,3,2,1,3,4 };
int sum = 0, carry;
int k = Num1.length + Num2.length;
int[] Num = new int[k];
for( int i = Num1.length - 1; i >= 0; i-- )
{
carry = 0;
for( int j = Num2.length - 1; j >= 0; j-- )
{
sum = Num2[j] * Num1[i] + carry + Num[k - 1];
carry = sum / 10;
Num[--k] = sum % 10;
}
Num[--k] = carry;
k += Num2.length;
}
for( int j = 0; j < Num.length; j++ )
{
System.out.println( j + "= " + Num[j] );
}
}
}