Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Very nice. My only issue is that c[0] will be null (or undefined) if there is a carry on the most significant digit.
@Michael - First assuming all values of the arrays are initialized to zero, the fact that c is of length maxlen+1 will avoid that problem (the new array will always be one digit longer than the longest input, allowing room to contain the correct sum after the final carry step).
Your solution is correct, but always increases the size of result by one, which is a design flaw. For example, if you have a=123 and b=256, c=a+b would be 0379 instead of 379. You can prevent it by just checking if summing two numbers will have a carry-on on the highest order digit or not by few lines of code.
Your solution also does not consider the fact that big numbers are signed or not signed.
Note that the question says the numbers are 'integers', meaning that they can be positive or negative. This code won't work as is when any or both or the numbers are negative. Like maybe the left-most cell in one of the number arrays contains a '-' character, indicating that the number is negative. We would most probably have to handle that in our code.
For fun because I wanted to act on a hunch that a few liner was possible. Though I expanded a line into multiple to make it clear that 3 possible cases of sum are being calculated.
Call this with b[] being bigger array, r[] having length b.length+1, and last argument 0
(use a wrapper if you like):
b stands for bigger, s for smaller, r for result
public int doit(int b[],int s[],int r[], int i)
{
if(i == b.length) return 0;
sum = doit(b,s,r,i+i) + ( i==0 ? 0 :
b.length-a.length >= i ? b[i-1] :
b[i-1] + a[i-1-a.length]);
r[i] = sum%10, return sum/10;
}
I used this diagram (in notepad) to play with to scratch my itch (the hunch):
i 4 5
res [ ][ ][ ][ ][ ][ ] res.length = b.length+1
b [ ][ ][ ][ ][ ]
a [ ][ ]
b.length-a.length=3
Yes, there are limitations to the design, but it looks cool (and different from the ones already posted). And probably has off by one errors.
Compiled on scrap paper, tested on that notepad diagram above.
Ughh careercup messed up alignments. Trying again:
public int doit(int b[],int s[],int r[], int i)
{
if(i == b.length) return 0;
sum = doit(b,s,r,i+i) + ( i==0 ? 0 :
b.length-a.length >= i ? b[i-1] :
b[i-1] + a[i-1-a.length]);
r[i] = sum%10, return sum/10;
}
And:
i 4 5
res [ ][ ][ ][ ][ ][ ]
b [ ][ ][ ][ ][ ]
a [ ][ ]
b.length-a.length=3
#include <stdio.h>
#include <stdlib.h>
int array_add(int *result, int data_1[], int len_1, int data_2[], int len_2){
if( len_1 < 0 || len_2 < 0 ){
return -1;
}
int i,j,k;
int temp;
// i = (len_1 < len_2 ? len_1-1:len_2-1);
temp = 0;
i = len_1 -1;
j = len_2 -1;
k = (len_1 > len_2 ? len_1:len_2);
for( ; i > -1 && j > -1 ; i--,j--){
temp = data_1[i] + data_2[j] +result[k];
result[k] = temp%10;
result[k-1] = result[k-1] + temp/10;
k--;
}
// j = (len_1 > len_2 ? len_1-len_2-1 : len_2-len_1-1);
if(i > -1){
while( i > -1 ){
temp = result[k] + data_1[i];
result[k] = temp%10;
result[k-1] = result[k-1] + temp/10;
i--;
k--;
}
}else if( j > -1 ){
while( j > -1 ){
temp = result[k]+ data_2[j];
result[k] = temp%10;
result[k-1] = result[k-1] + temp/10;
j--;
k--;
}
}
return 1;
}
int main(){
int array_1[5] = {2,3,4,6,7};
int array_2[6] = {5,7,2,7,8,3};
int i;
int *result = (int *)malloc(sizeof(int)*7);
for ( i = 0; i < 7 ; i++ ){
result[i] = 0;
}
array_add(result,array_1,5,array_2,6);
for ( i = 0; i < 7 ; i++ ){
printf("%d ",result[i]);
}
printf("\n");
return 1;
}
Not sure if I'm missing something or I misunderstood the problem but here is mine. It seems to work.
public class ArrayAddition {
public static void main(String[] args)
{
int[] a = {2, 6, 0, 0};
int[] b = {1, 7};
int finalArrayLength = Math.max(a.length, b.length); //returns the greater of the two lengths
int finalNum = addArray(a, b);
char[] result = Integer.toString(finalNum).toCharArray();
int[] finalArray = new int[finalArrayLength];
for (int i = 0; i < finalArray.length; i++)
{
finalArray[i] = Character.getNumericValue(result[i]);
}
System.out.println(Arrays.toString(finalArray));
}
public static int addArray(int[] a, int[] b)
{
String stringA = "";
String stringB = "";
int finalNum;
for (int i = 0; i < a.length; i++)
{
stringA += Integer.toString(a[i]);
}
for (int j = 0; j < b.length; j++)
{
stringB += Integer.toString(b[j]);
}
finalNum = Integer.parseInt(stringA) + Integer.parseInt(stringB);
return finalNum;
}
}
Well, here's a fun way of doing it, not really any more efficient than the other methods shown here, this one uses a stack.
int[] add_arrays(int[] a, int[] b){
Stack s = new Stack();
int pa = a.length;
int pb = b.length;
int carry = 0;
while(pa >= 0 || pb >= 0){
if(pa < 0){
s.push(b[pb] + carry);
carry = 0;
pb--;
continue;
}else if (pb < 0){
s.push(a[pa] + carry);
carry = 0;
pa--;
continue;
}else {
int x = a[pa] + b[pb] + carry;
if(x > 9){
carry = 1;
x %= 10;
}else {
carry = 0;
}
s.push(x);
pa--;
pb--;
}
}
int[] result = new int[s.length()];
for(int i = 0; !s.isEmpty(); i++){
result[i] = s.pop();
}
return result;
}
It will always take O(max(a.length,b.length)) time (so, O(n) where n is longest array's length). In no event will it have a extraneous digit on the front.
It's not a pretty or short solution, unfortunately, but it works and it is time efficient. It only works if you are adding in the following manner ( there is another version where the last digit is the highest)
{1,2,3} = 123.
{4,5,6} = 456.
{1,2,3} + {4,5,6} = 579
public static int[] AddArrays(int[] a, int lengtha, int[] b, int lengthb)
{
int[] result = new int[Math.Max(lengtha, lengthb) + 1];
int indexa = lengtha - 1;
int indexb = lengthb - 1;
int indexResult = result.Length - 1;
int carryOver = 0;
while (indexa >= 0 || indexb >= 0)
{
int valuea = 0;
int valueb = 0;
if (indexa >= 0)
{
valuea = a[indexa];
indexa--;
}
if (indexb >= 0)
{
valueb = b[indexb];
indexb--;
}
if (valuea / 10 > 0)
{
throw new ArgumentException();
}
if (valueb / 10 > 0)
{
throw new ArgumentException();
}
int tmp = valuea + valueb + carryOver;
result[indexResult] = tmp % 10;
carryOver = tmp / 10;
indexResult--;
}
if (indexResult != 0 && indexResult != 1)
{
throw new InvalidOperationException();
}
return result;
}
Java Solution:
private static int[] add(int[] one, int[] two) {
if (one == null || two == null)
throw new IllegalArgumentException("Parameters cannot be null.");
int size = Math.max(one.length, two.length) + 1;
int[] ret = new int[size];
boolean carry = false;
for (int i = 0; i < size; i++) {
int sum = 0;
if (carry) {
sum++;
carry = false;
}
if (i < one.length)
sum += one[i];
if (i < two.length)
sum += two[i];
if (sum >= 10) {
carry = true;
sum -= 10;
}
ret[size - i - 1] = sum;
}
return ret;
}
#include<iostream>
#include<math.h>
using namespace std;
void print(int * added_arr,int size )
{
for(int i=0; i<size; i++)
cout<<added_arr[i]<<",";
cout<<endl;
}
void sum(int * first_num, int * second_num, int size_of_1st_no ,int size_of_2st_no)
{
int add=0;
int i=0;
for( i=size_of_1st_no-1; size_of_2st_no-1>=0; i--)
{
add=first_num[i] + second_num[size_of_2st_no-1];
if(add>9)
{
first_num[i]=add%10; // store the result
first_num[i-1]=first_num[i-1] + 1; // in the case of carry adding
}
else
{
first_num[i]=add;
}
size_of_2st_no--;
}
if(i>0 && first_num[i] > 9 )
{
while(i>=0 && first_num[i] > 9)
{
first_num[i]=0;
first_num[i-1]=first_num[i-1]+1;
i--;
}
}
}
void main()
{
int size_of_1st_no=0;
int size_of_2st_no=0;
cout<<"Enter Size of first Array::";
cin>>size_of_1st_no;
cout<<"Enter Size of second Array::";
cin>>size_of_2st_no;
//---------Create arrys for both numbers. Number arry that is biger used to store the result later
int * first_num;
int * second_num;
if(size_of_1st_no >= size_of_2st_no)
{
size_of_1st_no=size_of_1st_no+1; // one index more in case of over flow
first_num=new int [size_of_1st_no];
second_num=new int [size_of_2st_no];
}
else
{
size_of_2st_no=size_of_2st_no+1; // one index more in case of over flow
first_num=new int [size_of_1st_no];
second_num=new int [size_of_2st_no];
}
int i=0;
int j=0;
if(size_of_1st_no >= size_of_2st_no)
{
i=1; j=0;
first_num[0]=0;
}
else
{
i=0; j=1;
second_num[0]=0;
}
for( ; i<size_of_1st_no;i++)
{
cout<<"Enter Element for First No:";
cin>>first_num[i];
}
for( ; j<size_of_2st_no;j++)
{
cout<<"Enter Element for Second No:";
cin>>second_num[j];
}
if(size_of_1st_no>size_of_2st_no)
sum(first_num, second_num,size_of_1st_no,size_of_2st_no);
else
sum(second_num, first_num,size_of_2st_no,size_of_1st_no);
if(size_of_2st_no>=size_of_1st_no)
print(second_num,size_of_2st_no);
else
print(first_num,size_of_1st_no);
//-----------------------------------------
system("pause");
}
alist = [1, 2, 4, 5, 6, 7]
blist = [9, 9, 3, 3, 2, 1, 9]
sumlist = []
alen = len(alist) - 1
blen = len(blist) - 1
carry = 0
while alen >= 0 or blen >= 0:
a = 0
b = 0
if alen >= 0:
a = alist[alen]
if blen >= 0:
b = blist[blen]
absum = (a + b + carry) % 10
carry = (a + b + carry) / 10
sumlist[:0] = [absum]
alen -= 1
blen -= 1
if carry > 0:
sumlist[:0] = [carry]
print sumlist
Java Solution
public class TwoArraySum {
public static int[] addArray(int[] a, int[] b){
int alen = a.length;
int blen = b.length;
int clen = Math.max(alen, blen);
int[] c = new int[clen];
boolean carry = false;
for ( int i = 0; i < clen; i++ ){
int eleSum = 0;
if ( i < alen ){
eleSum = a[i];
}
if ( i < blen){
eleSum += b[i];
}
if ( carry ){
eleSum += 1;
carry = false;
}
carry = (eleSum > 10);
c[i] = (carry)? eleSum-10 : eleSum;
}
return c;
}
public static void main(String[] args){
int[] b = new int[] { 6, 6, 6, 6, 6 };
int[] a = new int[] { 5, 0, 5 };
int[] c = addArray(a, b);
StringBuilder sb = new StringBuilder();
for ( int ele : c ){
sb.insert(0, ele);
}
System.out.println(sb.toString());
}
}
My intuitive algorithm:
vector<int> sum(vector<int> &a, vector<int> &b) {
int i, cary = 0;
int ap = a.size() - 1;
int bp = b.size() - 1;
int sz = 0;
//gets result size
while (ap >= 0 || bp >= 0) {
int d = 0;
if (ap >= 0)
d += a[ap--];
if (bp >= 0)
d += b[bp--];
d += cary;
cary = d / 10;
d %= 10;
sz++;
}
//Compute the sum
vector<int> ans(sz);
while (sz > 0) {
int d = 0;
if (ap >= 0)
d += a[ap--];
if (bp >= 0)
d += b[bp--];
d += cary;
cary = d / 10;
d %= 10;
ans[sz--] = d;
}
if (cary > 0)
ans[sz--] = cary;
reverse(ans.begin(), ans.end());
return ans;
}
The time complexity: O(max(|a|,|b|))
// assume the integers are positive
// 1-Select the size of the biggest array maxLen
// 2-Start the sum from the end of the selected array
// carry = 0;
// x goes from maxLen-1 to 0
// y = ( 0 or a[x] if x<aLen ) + ( 0 or b[x] if x<bLen ) + carry
// if y>9
// y = 10-y and carry = 1
// else
// carry = 0
int* Sum_array(unsigned int a[], std::size_t aLen, unsigned int b[], std::size_t bLen)
{
int maxLen = (aLen>bLen) ? aLen:bLen ;
int * Res = new int[maxLen+1];
std::size_t carry = 0;
for(int j=maxLen-1;j>=0;j--)
{
Res[j+1] = ((j<aLen) ? a[j]:0) + (( j<bLen ) ? b[j]:0) + carry;
if(Res[j+1]>9)
{
Res[j+1]=10-Res[j+1];
carry = 1;
}
else
{
carry = 0;
}
}
Res[0] = carry;
return Res;
}
I used long instead of int just so it could handle larger values.
public static void main(String arg[]) {
long[] arraySum1 = { 1, 2, 3, 4, 5, 1, 9, 8, 9, 3, 4 };
long[] arraySum2 = { 1, 2, 9, 4, 5, 2, 3, 8, 5 };
long arraySum = arraySum(arraySum1, arraySum2);
System.out.println(arraySum);
}
public static long arraySum(long[] x, long[] y) {
int a = x.length - 1, b = y.length - 1;
long sum = 0;
while (a >= 0 || b >= 0) {
if (a >= 0)
{sum += x[a] * Math.pow(10, x.length - a - 1);}
if (b >= 0)
{sum += y[b] * Math.pow(10, y.length - b - 1);}
System.out.println(sum);
a--; b--;
}
return sum;
}
I used long instead of int just so it could handle larger values.
public static void main(String arg[]) {
long[] arraySum1 = { 1, 2, 3, 4, 5, 1, 9, 8, 9, 3, 4 };
long[] arraySum2 = { 1, 2, 9, 4, 5, 2, 3, 8, 5 };
long arraySum = arraySum(arraySum1, arraySum2);
System.out.println(arraySum);
}
public static long arraySum(long[] x, long[] y) {
int a = x.length - 1, b = y.length - 1;
long sum = 0;
while (a >= 0 || b >= 0) {
if (a >= 0)
{sum += x[a] * Math.pow(10, x.length - a - 1);}
if (b >= 0)
{sum += y[b] * Math.pow(10, y.length - b - 1);}
System.out.println(sum);
a--; b--;
}
return sum;
}
Assuming arrays can be of different length:
int a[] = {9,5,7,2,4,8,5,9,1,5};
int b[] = {8,5,9,1};
int s, prev = 0, cA = sizeof(a)/sizeof(*a), cB = sizeof(b)/sizeof(*b);
int k = max(cA, cB), j;
int sum[k + 1];
for (int i = k - 1; i >= 0; i --){
s = prev;
j = (i - k + cA);
if (j >= 0 && j < cA){
s += a[j];
}
j = (i - k + cB);
if (j >= 0 && j < cB){
s += b[j];
}
prev = 0;
if (s > 9){
prev = (s / 10);
s %= 10;
}
sum[i] = s;
}
if (prev > 0){
sum[k] = prev;
}
else {
sum[k] = 0;//or remove the extra element
}
for (int i = 0; i < k; i ++){
printf("%d", sum[i]);
}
The numbers are stored from most sig digit to least from right to left in the array, as you'd probably naturally imagine.
int[] arr = {1, 2, 3}; // 123
The type of array is int[]. (This was originally in Java when asked).
public class Sum {
static int a1[] = {1,2,3,4};
static int a2[] = {9,9,9,9};
static int a3[];
static void findSum(int a1[], int a2[]){
int len1 = a1.length-1, len2 = a2.length-1, len3 = a3.length-1;
int carry = 0,sum;
while(len2 != -1){
sum = a1[len1--] + a2[len2--]+carry;
carry = sum / 10;
a3[len3--] = sum%10;
}
while(len1 != -1){
sum = a1[len1--] + carry;
a3[len3--] = sum%10;
carry = sum/10;
}
a3[len3] = carry;
for(int i = 0; i <a3.length; i++){
System.out.print(a3[i]);
}
}
public static void main(String args[]){
if(a1.length>a2.length){
a3 = new int[a1.length+1];
findSum(a1,a2);
}
else{
a3 = new int[a2.length+1];
findSum(a2,a1);
}
}
}
public static void main(String[] args) {
int[] a = {9,5,7,2,4,8,5,9,1,5};
int[] b = {9,1,1,1,2,3,8,5,9,1};
add(a,b);
}
static void add(int[] x, int[] y){
int xLength = x.length;
int yLength = y.length;
int zLength = Math.max(xLength, yLength)+1;
int[] z = new int[zLength];
int k = 0;
for (int i=1;i<=zLength;i++){
if(xLength-i<0 && yLength-i>=0){
z[zLength-i] = (y[yLength-i]+k)%10;
k = (y[yLength-i]+k)/10;
}
else if(yLength-i<0 && xLength-i>=0){
z[zLength-i] = (x[xLength-i]+k)%10;
k = (x[xLength-i]+k)/10;
}
else if(yLength-i<0 && xLength-i<0){
z[zLength-i] = k;
}
else if(yLength-i>=0 && xLength-i>=0){
z[zLength-i] = (x[xLength-i]+y[yLength-i]+k)%10;
k = (x[xLength-i]+y[yLength-i]+k)/10;
}
}
for (int i=0;i<zLength;i++){
System.out.print(z[i]);
}
System.out.println();
}
#!/usr/bin/env python
def getVal(tlist, i):
if i < len(tlist):
return tlist[i]
else:
return 0
def addNum(list1,list2):
total = list()
carryOn = 0
index1 = len(list1)-1
index2 = len(list2)-1
while index1 >= 0 and index2 >= 0:
tsum = list1[index1] + list2[index2] + carryOn
total.append(tsum%10)
carryOn = int(tsum/10)
index1-=1
index2-=1
print total,index1,index2
if index2 < 0:
while index1 >=0:
tsum = carryOn + list1[index1]
total.append(tsum%10)
carryOn = int(tsum/10)
index1-=1
print total
else:
while index2 >=0:
tsum = carryOn + list2[index2]
total.append(tsum%10)
carryOn = int(tsum/10)
index2-=1
return total[::-1]
if __name__ == '__main__':
list1 = [1,2,3,4,8]
list2 = [3,7,8,9,2,3,4]
print addNum(list1,list2)
No need for so much duplicated code. Check this:
def sum_big(a, b):
c = [0 for it in xrange(max(len(a),len(b))+1)]
it_a = len(a) - 1
it_b = len(b) - 1
it_c = len(c) - 1
carry = 0
while it_c >= 0:
s = carry
if it_a >= 0:
s += a[it_a]
if it_b >= 0:
s += b[it_b]
c[it_c] = s % 10
carry = s / 10
it_a -= 1
it_b -= 1
it_c -= 1
return c
- mindless monk October 24, 2013