Microsoft Interview Question Applications Developers
Country: India
Interview Type: In-Person
The solution has the complexity of O(nm) while n is the digit number of the first number and m is the second one.
#define toAscii(A,len) for(int i=0; i<len; A[i++]+='0');
#define fromAscii(A,len) for(int i=0; i<len; A[i++]-='0');
char * multiply(char *A, char*B)
{
int n= strlen(A);
int m = strlen(B);
char * res = (char*) malloc (sizeof(char)*n+m+1);
memset(res, 0, sizeof(char)*n+m+1);
fromAscii(A,n);
fromAscii(B,m);
for(int i=n-1; i>=0; i--)
for(int j=m-1; j>=0; j--)
{
res[i+j+1]+=(A[i] * B[j]);
res[i+j]+=res[i+j+1]/10;
res[i+j+1] = res[i+j+1]%10;
}
toAscii(res, n+m+1);
res[n+m]='\0';
return res;
}
There are also faster algorithms. There's a simple to understand one that runs in n ^ (log base 2 of 3) when n is the size of m, and then the fast Fourier transform, which runs in n*log(n).
#include<iostream>
#include<string.h>
using namespace std;
void add(char *a, char *b, char *c)
{
int i, cc=0,m=strlen(a)>strlen(b)?strlen(a):strlen(b),k,s;
k=s=strlen(a)<strlen(b)?strlen(a):strlen(b);
k-=1;m--;s--;
if(strlen(a)>strlen(b)?1:0)
{
for(i=m;i>=m-s;--i,k--)
{
c[i]=((int)(a[i])+(int)(b[k])-48*2+cc)%10+48;
cc=((int)(a[i])+(int)(b[k])-48*2)>9?1:0;
}
for(;i>=0;--i)
{
c[i]=((int)a[i]+cc-48)%10+48;
cc=((int)(a[i])+cc-48)>9?1:0;
}
}
else
{
for(i=m;i>=m-s;--i,k--)
{
c[i]=((int)(a[k])+(int)(b[i])-48*2+cc)%10+48;
cc=((int)(a[k])+(int)(b[i])-48*2)>9?1:0;
}
for(;i>=0;--i)
{
c[i]=((int)b[i]+cc-48)%10+48;
cc=((int)(b[i])+cc-48)>9?1:0;
}
}
}
main()
{
char a[]="111000",b[]="110001",*c;
c= new char[strlen(a)>strlen(b)?strlen(a):strlen(b)];
add(a,b,c);
cout<<c<<endl;
}
public static int[] multiplyBigNumbers(int[] num1, int[] num2) {
int[] result = new int[num1.length + num2.length];
int carry = 0;
int offset = 0;
for (int i = num1.length - 1; i >= 0; i--) {
int tail = result.length - 1 - offset;
for (int j = num2.length - 1; j >= 0; j--) {
int sum = result[tail] + (num1[i] * num2[j]) + carry;
result[tail] = sum % 10;
carry = sum / 10;
tail--;
}
if (carry > 0) {
addCarry(result, tail, carry);
carry = 0;
}
offset++;
}
return result;
}
private static void addCarry(int[] result, int tail, int carry) {
result[tail] += carry;
while (result[tail] >= 10) {
carry = result[tail] / 10; // add carry
result[tail] = result[tail] % 10;
result[--tail] += carry;
}
}
public static void main(String[] args) {
int[] num1 = {9, 9, 9, 9, 9};
int[] num2 = {9, 9, 9, 9, 9};
int[] result = multiplyBigNumbers(num1, num2);
System.out.println("Result: ");
for (int i : result) {
System.out.print(i + " ");
}
}
int *multiply(char *a,char *b)
{
int* c = (int *)malloc(strlen(a)+ strlen(b));
memset(c, 0, sizeof(int) * (strlen(a) + strlen(b)));
int carry,bi,ai;
for(bi = strlen(b)-1; bi>=0; bi--){
carry = 0;
for(ai = strlen(a)-1; ai >=0; ai--){
c[ai + bi + 1] += carry + (a[ai]-'0')*(b[bi]-'0');
carry = c[ai + bi + 1]/10;
c[ai + bi + 1] = c[ai + bi + 1] % 10;
}
c[bi]= carry;
}
return c;
}
main()
{
char* a = "55555555";
char* b = "3333333333";
int* c1 = (int *)malloc(strlen(a) + strlen(b));
c1 = multiply(a,b);
for(int i=0;i < strlen(a) + strlen(b); i++)
printf("%d", c1[i]);
}
public class BigMultiplication {
public static void main(String[] args) {
String s1 = "99";
String s2 = "999";
int result = Integer.valueOf(new BigMultiplication().multiply(s1, s2));
System.out.println(s1 + "*" + s2 + "=" + result);
}
private String multiply(String s1, String s2) {
char[] n1 = s1.toCharArray();
char[] n2 = s2.toCharArray();
int size1 = s1.length();
int size2 = s2.length();
int[][] out = new int[size2][size1+1]; // extra size for one remainder
StringBuilder mainResult = new StringBuilder();
int previousRemainder = 0;
// make a 2D array of multiplication where each row denote n1*(a digit
// of n2 starting from the unit place digit)
for (int j = size2 - 1; j >= 0; j--) { //for each character of of 2nd number
previousRemainder=0;
for (int i = size1 - 1; i >= 0; i--) { // multiply with each character of first array
int data = (Character.getNumericValue(n2[j]) * Character.getNumericValue(n1[i])) + previousRemainder;
previousRemainder = data / 10; // if the multiplication gives result >= 10 fin the remainder and preserve it to be added to the next multiplication
int actualData = data % 10; // get the actual data at unit place of the multiplication
if(i==0){
out[size2 - 1 - j][size1 - 1 - i] = actualData;
out[size2 - 1 - j][size1 - i] = previousRemainder; // for last multiplication put the remainder also in the matrix
}else{
out[size2 - 1 - j][size1 - 1 - i] = actualData; // set the actual data in a 2D matrix starting from index (0,0)
}
}
}
// the 2D array so formed is:
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
System.out.print(out[i][j] + "\t");
}
System.out.println();
}
/**
* this array will contain the sum of diagoinal elements. the logic
* behind is that in a 2D array, on any diagonal the sum of indices
* (i+j) is always constant & (i+j) varies fro 0 to (row +column)
*
*/
int[] rawResult = new int[size1 + size2 + 1];
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
rawResult[i + j] += out[i][j];
}
}
previousRemainder = 0;
for (int i = 0; i < rawResult.length; i++) {
int data = rawResult[i] + previousRemainder;
mainResult.append(String.valueOf((data % 10)));
previousRemainder = data / 10;
}
return mainResult.reverse().toString();
}
}
package demo;
public class BigMultiplication {
public static void main(String[] args) {
String s1 = "99";
String s2 = "999";
int result = Integer.valueOf(new BigMultiplication().multiply(s1, s2));
System.out.println(s1 + "*" + s2 + "=" + result);
}
private String multiply(String s1, String s2) {
char[] n1 = s1.toCharArray();
char[] n2 = s2.toCharArray();
int size1 = s1.length();
int size2 = s2.length();
int[][] out = new int[size2][size1+1]; // extra size for one remainder
StringBuilder mainResult = new StringBuilder();
int previousRemainder = 0;
// make a 2D array of multiplication where each row denote n1*(a digit
// of n2 starting from the unit place digit)
for (int j = size2 - 1; j >= 0; j--) { //for each character of of 2nd number
previousRemainder=0;
for (int i = size1 - 1; i >= 0; i--) { // multiply with each character of first array
int data = (Character.getNumericValue(n2[j]) * Character.getNumericValue(n1[i])) + previousRemainder;
previousRemainder = data / 10; // if the multiplication gives result >= 10 fin the remainder and preserve it to be added to the next multiplication
int actualData = data % 10; // get the actual data at unit place of the multiplication
if(i==0){
out[size2 - 1 - j][size1 - 1 - i] = actualData;
out[size2 - 1 - j][size1 - i] = previousRemainder; // for last multiplication put the remainder also in the matrix
}else{
out[size2 - 1 - j][size1 - 1 - i] = actualData; // set the actual data in a 2D matrix starting from index (0,0)
}
}
}
// the 2D array so formed is:
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
System.out.print(out[i][j] + "\t");
}
System.out.println();
}
/**
* this array will contain the sum of diagoinal elements. the logic
* behind is that in a 2D array, on any diagonal the sum of indices
* (i+j) is always constant & (i+j) varies fro 0 to (row +column)
*
*/
int[] rawResult = new int[size1 + size2 + 1];
for (int i = 0; i < out.length; i++) {
for (int j = 0; j < out[i].length; j++) {
rawResult[i + j] += out[i][j];
}
}
previousRemainder = 0;
for (int i = 0; i < rawResult.length; i++) {
int data = rawResult[i] + previousRemainder;
mainResult.append(String.valueOf((data % 10)));
previousRemainder = data / 10;
}
return mainResult.reverse().toString();
}
}
using System;
public class Program
{
public static void Main()
{
Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999"));
}
public static string GetProduct(string s1,string s2)
{
int digit1=0;
int digit2=0;
char[] str1=s1.ToCharArray();
char[] str2=s2.ToCharArray();
int carry;
string[] result=new string[str1.Length];
string finalproduct=string.Empty;
int padding=0;
for(int i=str1.Length-1;i>=0;i--)
{
digit1=str1[i]-'0';
string resval=string.Empty;
carry=0;
int j;
for(j=str2.Length-1;j>=0;j--)
{
digit2=str2[j]-'0';
int product=digit1*digit2+carry;
carry=product/10;
resval=resval+(product%10);
}
if(carry>0)
{
resval=resval+carry;
}
for(int k=0;k<padding;k++)
{
resval="0"+resval;
}
result[i]=resval;
padding++;
}
int max=findMax(result);
int count=0;
int car=0;
while(count<max)
{
int sum=0;
for(int x=0;x<result.Length;x++)
{
if(count<result[x].Length)
{
sum+=result[x][count]-'0';
}
}
sum+=car;
car=sum/10;
int p=sum%10;
finalproduct=p+finalproduct;
count++;
}
finalproduct=car+finalproduct;
return finalproduct.TrimStart('0');
}
public static int findMax(string[] s)
{
int max=0;
for(int i=0;i<s.Length;i++)
{
int len=s[i].Length;
max=Math.Max(max,len);
}
return max;
}
}
- hao.liu0708 August 26, 2012#include <iostream> void multipy(char* a, char* b, char* res) { int lenA = strlen(a); int lenB = strlen(b); int i, j; int* c = new int[lenA + lenB]; memset(c, 0, sizeof(int) * (strlen(a) + strlen(b))); for (i = lenA - 1; i >= 0; i--) for (j = lenB - 1; j >= 0; j--) c[i + j + 1] += (b[j] - '0') * (a[i] - '0'); for (i = lenA + lenB - 1; i >= 0; i--) { if (c[i] >= 10) { c[i - 1] += c[i] / 10; c[i] %= 10; } } i = 0; while (c[i] == 0) i++; j = 0; while (i < lenA + lenB) { res[j] = c[i] + '0'; i++; j++; } res[j] = 0; delete[] c; }; int main() { char* a = "999"; char* b = "9999"; char* res = new char[strlen(a) + strlen(b)]; multipy(a, b, res); return 0; }