Google Interview Question Interns
Team: -
Country: United States
Interview Type: Phone Interview
vector<char> AddVectors(vector<char>& a, vector<char>& b)
{
char carry = 0;
vector<char> result;
vector<char>::reverse_iterator aIt = a.rbegin();
vector<char>::reverse_iterator bIt = b.rbegin();
for (; aIt != a.rend() && bIt != b.rend(); aIt++, bIt++) {
result.push_back((*aIt + *bIt + carry) % 10);
carry = (*aIt + *bIt + carry) / 10;
}
if (aIt != a.rend()) {
result.push_back((*aIt + carry) % 10);
carry = (*aIt + carry) / 10;
}
if (bIt != b.rend()) {
result.push_back((*bIt + carry) % 10);
carry = (*bIt + carry) / 10;
}
if (carry > 0)
result.push_back(carry);
reverse(result.begin(), result.end());
return result;
}
That will works only if the array can be converted to an integer. If the length of array is longer than the value an int/Integer can hold, that won't work.
For ex. {1,2,3,4,5,6,7,8,9,10,11,12,12,13,14,15,16,17,1,8} + {1,2,3} won't work
But yes, for the examples in the problem statement, it will work.
This solution works for all the above examples stated in the problem statement.
The only difference is that it appends an extra '0' in the front if there is no carry over
public class ArraySumElementWiseDemo {
static int[] addArraysElementWise(int[] array1, int[] array2) {
int auxResultArrayLength;
int[] smallerArray;
int[] biggerArray;
int[] emptyArray = {};
if(array1.length == 0 && array2.length == 0) return emptyArray;
if(array1.length == 0) return array2;
if(array2.length == 0) return array1;
if (array1.length >= array2.length) {
auxResultArrayLength = array1.length + 1; //+1 to store the carry over
biggerArray = array1;
smallerArray = array2; //to traverse only until the smaller array
} else {
auxResultArrayLength = array2.length + 1; //+1 to store the carry over in case needed
biggerArray = array2;
smallerArray = array1;
}
int[] auxResultArray = new int[auxResultArrayLength];
int carryOver = 0;
int tempSum = 0; //to store temporary sum
for (int i = smallerArray.length -1, j = biggerArray.length -1 ;i > -1; i--, j--) {
tempSum = smallerArray[i] + biggerArray[j] + carryOver;
if (tempSum < 10) {
auxResultArray[j+1] = tempSum;
carryOver = 0;
} else {
carryOver = 1;
auxResultArray[j+1] = tempSum - 10;
}
}
//Now add carry on to the bigger array and keep on copying the bigger array + carryOver to the auxResultArray
for (int j = biggerArray.length - smallerArray.length - 1; j > -1; j--) {
tempSum = biggerArray[j] + carryOver;
if (tempSum < 10) {
auxResultArray[j+1] = tempSum;
carryOver = 0;
} else {
carryOver = 1;
auxResultArray[j+1] = tempSum - 10;
}
}
//Add the carry over to the first element of auxResultArray
auxResultArray[0] = carryOver;
return auxResultArray;
}
public static void main(String[] args) {
int[] array1 = {1,2,3};
int[] array2 = {2,3,4} ;
System.out.println(Arrays.toString(addArraysElementWise(array1, array2)));
}
}
public class ArraySumElementWiseDemo {
static int[] addArraysElementWise(int[] array1, int[] array2) {
int auxResultArrayLength;
int[] smallerArray;
int[] biggerArray;
int[] emptyArray = {};
if(array1.length == 0 && array2.length == 0) return emptyArray;
if(array1.length == 0) return array2;
if(array2.length == 0) return array1;
if (array1.length >= array2.length) {
auxResultArrayLength = array1.length + 1; //+1 to store the carry over
biggerArray = array1;
smallerArray = array2; //to traverse only until the smaller array
} else {
auxResultArrayLength = array2.length + 1; //+1 to store the carry over in case needed
biggerArray = array2;
smallerArray = array1;
}
int[] auxResultArray = new int[auxResultArrayLength];
int carryOver = 0;
int tempSum = 0; //to store temporary sum
for (int i = smallerArray.length -1, j = biggerArray.length -1 ;i > -1; i--, j--) {
tempSum = smallerArray[i] + biggerArray[j] + carryOver;
if (tempSum < 10) {
auxResultArray[j+1] = tempSum;
carryOver = 0;
} else {
carryOver = 1;
auxResultArray[j+1] = tempSum - 10;
}
}
//Now add carry on to the bigger array and keep on copying the bigger array + carryOver to the auxResultArray
for (int j = biggerArray.length - smallerArray.length - 1; j > -1; j--) {
tempSum = biggerArray[j] + carryOver;
if (tempSum < 10) {
auxResultArray[j+1] = tempSum;
carryOver = 0;
} else {
carryOver = 1;
auxResultArray[j+1] = tempSum - 10;
}
}
//Add the carry over to the first element of auxResultArray
auxResultArray[0] = carryOver;
return auxResultArray;
}
public static void main(String[] args) {
int[] array1 = {1,2,3};
int[] array2 = {2,3,4} ;
System.out.println(Arrays.toString(addArraysElementWise(array1, array2)));
}
}
Only minor differnece is that if there is no carry over, this algorithm still appends 0 in the beginning.
vector<int> find_sum(vector<int> a,vector<int>b){
vector<int> result;
vector<int> ::iterator it;
int p_a=a.size()-1;
int p_b=b.size()-1;
int sum=0;int carry=0;
while(p_a>=0 || p_b>=0){
sum=carry;
if(p_a>=0){
sum=sum+a[p_a];
p_a--;
}
if(p_b>=0){
sum=sum+b[p_b];
p_b--;
}
carry=(int)sum/10;
sum=sum%10;
cout<<"sum="<<sum<<" carry"<<carry<<endl;
//result.resize(result.size()+1);
it=result.begin();
result.insert(it,1,sum);
}
if (carry>0){
it=result.begin();
result.insert(it,1,carry);
}
return result;
}
int i = 0;
int carry =0;
int arr1_length = arr1.length - 1;
int arr2_length = arr2.length - 1;
StringBuffer sb = new StringBuffer();
while (i <= arr1_length && i <= arr2_length) {
int sum = arr1[arr1_length - i] + arr2[arr2_length - i]+carry;
if(sum>=10){
carry = sum/10;
sum = sum%10;
}
sb.append(sum);
// System.out.println(sum);
i++;
}
if(carry!=0)
sb.append(carry);
while (i <= arr1_length) {
sb.append(arr1[arr1_length - i]);
i++;
}
while (i <= arr2_length) {
sb.append(arr2[arr2_length - i]);
i++;
}
System.out.println("final result:" + sb.reverse().toString());
{
int i = 0;
int carry =0;
int arr1_length = arr1.length - 1;
int arr2_length = arr2.length - 1;
StringBuffer sb = new StringBuffer();
while (i <= arr1_length && i <= arr2_length) {
int sum = arr1[arr1_length - i] + arr2[arr2_length - i]+carry;
if(sum>=10){
carry = sum/10;
sum = sum%10;
}
sb.append(sum);
// System.out.println(sum);
i++;
}
if(carry!=0)
sb.append(carry);
while (i <= arr1_length) {
sb.append(arr1[arr1_length - i]);
i++;
}
while (i <= arr2_length) {
sb.append(arr2[arr2_length - i]);
i++;
}
System.out.println("final result:" + sb.reverse().toString());
}
c# implementation.
namespace DigitSum {
class Program {
static private int[] GetDigitSum( int[] arr1, int[] arr2 ) {
string str = string.Empty;
int mem = 0;
int counter = 0;
while ( true ) {
var index1 = arr1.Length - counter - 1;
var index2 = arr2.Length - counter - 1;
if ( index1 < 0 && index2 < 0 && mem == 0 ) {
break;
}
int s1 = index1 < 0 ? 0 : arr1[ index1 ];
int s2 = index2 < 0 ? 0 : arr2[ index2 ];
if ( s1 > 9 || s2 > 9 || s1 < 0 || s2 < 0 ) {
throw new Exception("Error");
}
int sum = s1 + s2 + mem;
if (sum > 9) {
sum -= 10;
mem = 1;
} else {
mem = 0;
}
str = sum + str;
counter++;
}
int[] res = new int[ str.Length ];
for ( int i = 0; i < str.Length; i++ ) {
res[ i ] = int.Parse( str[ i ].ToString() );
}
return res;
}
static void Main(string[] args)
{
GetDigitSum(new int[] {1,2,3}, new int[] {5,5,9,9,2,3});
}
}
}
Python Implementation:
{{
def sumArray(a,b):
'''Given two arrays, sum them pointwise with carryover'''
ret = []
diff_len = len(a) - len(b)
rev_a = a[::-1]
rev_b = b[::-1]
if diff_len > 0:
rev_b.extend([0]*diff_len)
elif diff_len < 0:
rev_a.extend([0]*abs(diff_len))
appendSum = 0
for i,a_val in enumerate(rev_a):
b_val = rev_b[i]
sum = b_val + a_val + appendSum
if sum >= 10:
ret.append(sum % 10)
appendSum = 1
else:
ret.append(sum + appendSum)
appendSum = 0
if i == len(rev_a) - 1 and appendSum == 1:
ret.append(1)
}}
Python:
{{
def sumArray(a,b):
'''Given two arrays, sum them pointwise with carryover'''
ret = []
diff_len = len(a) - len(b)
rev_a = a[::-1]
rev_b = b[::-1]
if diff_len > 0:
rev_b.extend([0]*diff_len)
elif diff_len < 0:
rev_a.extend([0]*abs(diff_len))
appendSum = 0
for i,a_val in enumerate(rev_a):
b_val = rev_b[i]
sum = b_val + a_val + appendSum
if sum >= 10:
ret.append(sum % 10)
appendSum = 1
else:
ret.append(sum + appendSum)
appendSum = 0
if i == len(rev_a) - 1 and appendSum == 1:
ret.append(1)
}}
The following code does not implement carry forward**
import java.util.Arrays;
public class a1 {
public a1() {
// TODO Auto-generated constructor stub
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] a1=new int[3];
//int[] b1=new int[3];
int[] a1={1,2,3,4};
int[] b1={1,2,3,1,1};
int la=a1.length;
int lb=b1.length;
if(la>lb)
{
int diff=la-lb;
int[] nb1=Arrays.copyOf(b1,lb+diff);
int[] c1=new int[la];
for(int i=0;i<la;i++)
{
c1[i]=a1[i]+nb1[i];
}
for(int i=0;i<c1.length;i++)
{
System.out.println(c1[i]);
}
}
else
{
int diff=lb-la;
int[] na1=Arrays.copyOf(a1,la+diff);
int[] c1=new int[lb];
for(int i=0;i<lb;i++)
{
c1[i]=na1[i]+b1[i];
}
for(int i=0;i<c1.length;i++)
{
System.out.println(c1[i]);
}
}
}
}
/* take 2 int arrays of any size and return the array that calculates the sum of both
*
* did not implement carry forward example a1={9,5} b1={2,3} then result={1,1,8}*/
import java.util.Arrays;
public class a1 {
public a1() {
// TODO Auto-generated constructor stub
}
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] a1=new int[3];
//int[] b1=new int[3];
int[] a1={9,5};
int[] b1={2,3};
int la=a1.length;
int lb=b1.length;
if(la>lb)
{
int diff=la-lb;
int[] nb1=Arrays.copyOf(b1,lb+diff);
int[] c1=new int[la];
for(int i=0;i<la;i++)
{
c1[i]=a1[i]+nb1[i];
if(c1[i]>10)
{
int flag=1;
}
}
for(int i=0;i<c1.length;i++)
{
System.out.println(c1[i]);
}
}
else
{
int diff=lb-la;
int[] na1=Arrays.copyOf(a1,la+diff);
int[] c1=new int[lb];
for(int i=0;i<lb;i++)
{
c1[i]=na1[i]+b1[i];
}
for(int i=0;i<c1.length;i++)
{
System.out.println(c1[i]);
}
}
}
}
Just create one new array with size max + 1, where max is max size of two given arrays.
and starting from the end of both array add elements, save to new array the remainder when sum divided by 10, and save to temp variable carry.
import java.util.*;
public class AddArrays {
public static void main(String... args) {
int[] a = {9, 9, 9};
int[] b = {9, 9, 9, 9, 9};
int[] sum = sum(a, b);
System.out.println(Arrays.toString(sum));
}
private static int[] sum(int[] a, int[] b) {
int al = a.length;
int bl = b.length;
if (al < bl) {
return sum(b, a);
}
int[] sum = new int[al + 1];
int carry = 0;
int s;
for (int i = al - 1; i >= 0; i--) {
s = carry;
if (i - al + bl >= 0) {
s += b[i - al + bl];
}
s += a[i];
sum[i + 1] = s % 10;
carry = s / 10;
}
sum[0] = carry;
return sum;
}
}
Following is the python code:
def intSum(A,B):
carry = 0
C = []
i = len(A)-1
j = len(B)-1
while(i>=0 and j>=0):
a = A[i]
b = B[j]
sum = a+b+carry
if(sum<10):
C.append(sum)
carry = 0
else:
carry = 1
sum = sum%10
C.append(sum)
i -= 1
j -= 1
while(j>=0):
b = B[j]
sum = b+carry
if(sum<10):
C.append(sum)
carry = 0
else:
carry = 1
sum = sum%10
C.append(sum)
j -= 1
while(i>=0):
a = A[i]
sum = a+carry
if(sum<10):
C.append(sum)
carry = 0
else:
carry = 1
sum = sum%10
C.append(sum)
i -= 1
if(carry!=0):
C.append(carry)
C.reverse()
return C
print intSum([9,9,9,9],[1,1,3])
Python Code:
def intSum(A,B):
carry = 0
C = []
i = len(A)-1
j = len(B)-1
while(i>=0 and j>=0):
a = A[i]
b = B[j]
sum = a+b+carry
if(sum<10):
C.append(sum)
carry = 0
else:
carry = 1
sum = sum%10
C.append(sum)
i -= 1
j -= 1
while(j>=0):
b = B[j]
sum = b+carry
if(sum<10):
C.append(sum)
carry = 0
else:
carry = 1
sum = sum%10
C.append(sum)
j -= 1
while(i>=0):
a = A[i]
sum = a+carry
if(sum<10):
C.append(sum)
carry = 0
else:
carry = 1
sum = sum%10
C.append(sum)
i -= 1
if(carry!=0):
C.append(carry)
C.reverse()
return C
print intSum([9,9,9,9],[1,1,3])
The tricky part is that we need to return an array, and can be a carry in my solution I add the two arrays and put the result in an integer variable so I can know if there is carry and the exact length of the resulting array. The last thing is to put back the variable in the resulting array. This will be more easy if we can return an array with and extra cell for a possible carry.
public int[] AddArrays(int[] a1, int[] a2)
{
if (a1 == null || a1.Length == 0)
return a2;
if (a2 == null || a2.Length == 0)
return a1;
int n = 0;
bool carry = false;
int length = Math.Max(a1.Length, a2.Length);
int index1 = a1.Length - 1;
int index2 = a2.Length - 1;
int i = 1;
while (index1 >= 0 || index2 >= 0)
{
int v1 = (index1 >= 0) ? a1[index1] : 0;
int v2 = (index2 >= 0) ? a2[index2] : 0;
int v = v1 + v2;
if (carry)
v++;
carry = v >= 10;
n += i * (v % 10);
i *= 10;
index1--;
index2--;
}
if (carry)
{
length++;
n += 1 * i;
}
int[] result = new int[length];
int index = length - 1;
while (n > 0)
{
result[index] = n % 10;
index--;
n /= 10;
}
return result;
}
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main()
{
vector<int> vc1;
vector<int> vc2;
deque<int> dq;
int n,i,t=0,cr=0,x;
cout<<"limit";
cin>>n;
cout<<"first array";
for(i=0;i<n;i++)
{
cin>>x;
vc1.push_back(x);
}
cout<<"second array";
for(i=0;i<n;i++)
{
cin>>x;
vc2.push_back(x);
}
for(i=vc1.size()-1;i>=0;i--)
{
t=vc1[i]+vc2[i]+cr;
if(t<10)
{
dq.push_front(t);
cr=0;
}
else
{
cr=1;
dq.push_front(t-10);
}
}
for(i=0;i<dq.size();i++)
{
cout<<dq[i];
}
}
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main()
{
vector<int> vc1;
vector<int> vc2;
deque<int> dq;
int n,i,t=0,cr=0,x;
cout<<"limit";
cin>>n;
cout<<"first array";
for(i=0;i<n;i++)
{
cin>>x;
vc1.push_back(x);
}
cout<<"second array";
for(i=0;i<n;i++)
{
cin>>x;
vc2.push_back(x);
}
for(i=vc1.size()-1;i>=0;i--)
{
t=vc1[i]+vc2[i]+cr;
if(t<10)
{
dq.push_front(t);
cr=0;
}
else
{
cr=1;
dq.push_front(t-10);
}
}
for(i=0;i<dq.size();i++)
{
cout<<dq[i];
}
}
import java.util.ArrayList;
/*
Write a method that takes in 2 int arrays of any size
and returns an array that calculates the sum of both
*/
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
int[] first = {9,9,2};
int[] second = {0,1,3};
Integer[] summed = calculateSum(first, second);
for(int x: summed) {
System.out.print(x + " ");
}
}
/*
Write a method that takes in 2 int arrays of any size
and returns an array that calculates the sum of both
[1,2,3] and [2,3,4] will return [3,5,7]
[9,9,2] and [0,1,3] - carry sum [1,0,0,5]
** Single digit only
*/
public static Integer[] calculateSum(int[] first, int[] second) {
ArrayList<Integer> summed = new ArrayList<Integer>();
for(int i=0; i<first.length; i++) {
int sum = first[i] + second[i];
if(sum < 10) {
summed.add(sum);
} else {
superAdd(summed, sum);
}
}
Integer arr[] = new Integer[summed.size()];
return summed.toArray(arr);
}
private static void superAdd(ArrayList<Integer> summed, int sum) {
int rmdr = sum%10;
//remove last element
if(summed.isEmpty()) {
summed.add(1);
} else {
int last = summed.remove(summed.size() - 1);
last += 1;
if (last < 10) {
summed.add(last);
} else {
superAdd(summed, last);
}
}
summed.add(rmdr);
}
}
import java.util.ArrayList;
/*
Write a method that takes in 2 int arrays of any size
and returns an array that calculates the sum of both
*/
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
int[] first = {9,9,2};
int[] second = {0,1,3};
Integer[] summed = calculateSum(first, second);
for(int x: summed) {
System.out.print(x + " ");
}
}
/*
Write a method that takes in 2 int arrays of any size
and returns an array that calculates the sum of both
[1,2,3] and [2,3,4] will return [3,5,7]
[9,9,2] and [0,1,3] - carry sum [1,0,0,5]
** Single digit only
*/
public static Integer[] calculateSum(int[] first, int[] second) {
ArrayList<Integer> summed = new ArrayList<Integer>();
for(int i=0; i<first.length; i++) {
int sum = first[i] + second[i];
if(sum < 10) {
summed.add(sum);
} else {
superAdd(summed, sum);
}
}
Integer arr[] = new Integer[summed.size()];
return summed.toArray(arr);
}
private static void superAdd(ArrayList<Integer> summed, int sum) {
int rmdr = sum%10;
//remove last element
if(summed.isEmpty()) {
summed.add(1);
} else {
int last = summed.remove(summed.size() - 1);
last += 1;
if (last < 10) {
summed.add(last);
} else {
superAdd(summed, last);
}
}
summed.add(rmdr);
}
}
package practice;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class Practice {
public static void main(String[] args) {
Random random;
int[] firstArray, secondArray;
random = new Random();
firstArray = new int[random.nextInt(10) + 1];
secondArray = new int[random.nextInt(10) + 1];
for (int i = 0; i < firstArray.length; i++) {
firstArray[i] = random.nextInt(10);
}
for (int i = 0; i < secondArray.length; i++) {
secondArray[i] = random.nextInt(10);
}
System.out.println(Arrays.toString(firstArray));
System.out.println(Arrays.toString(secondArray));
System.out.println(Arrays.toString(sumTwoArrays(firstArray, secondArray)));
}
public static int[] sumTwoArrays(int[] firstArray, int[] secondArray) {
int indexOfFirstArray, indexOfSecondArray;
int[] returnedArray;
ArrayList<Integer> integerArrayList;
if (firstArray == null || firstArray.length == 0 || secondArray == null || secondArray.length == 0) {
return null;
}
indexOfFirstArray = firstArray.length - 1;
indexOfSecondArray = secondArray.length - 1;
integerArrayList = new ArrayList();
integerArrayList.add(0, 0);
do {
if (indexOfFirstArray >= 0 && indexOfSecondArray >= 0) {
integerArrayList.add(1, firstArray[indexOfFirstArray] + secondArray[indexOfSecondArray]);
} else if (indexOfFirstArray >= 0 && indexOfSecondArray < 0) {
integerArrayList.add(1, firstArray[indexOfFirstArray]);
} else {
integerArrayList.add(1, secondArray[indexOfSecondArray]);
}
if (indexOfFirstArray >= 0) {
indexOfFirstArray--;
}
if (indexOfSecondArray >= 0) {
indexOfSecondArray--;
}
} while (indexOfFirstArray >= 0 || indexOfSecondArray >= 0);
for (int i = integerArrayList.size() - 1; i >= 0; i--) {
if (integerArrayList.get(i) >= 10) {
integerArrayList.set(i, integerArrayList.get(i) % 10);
integerArrayList.set(i - 1, integerArrayList.get(i - 1) + 1);
}
}
if (integerArrayList.get(0) == 0) {
integerArrayList.remove(0);
}
returnedArray = new int[integerArrayList.size()];
for (int i = 0; i < integerArrayList.size(); i++) {
returnedArray[i] = integerArrayList.get(i);
}
return returnedArray;
}
}
Solution that runs o(n):
int* arrSum(int i0[], int &s0, int i1[], int s1) //accepts array1, size of array1, array2 and size of array2
{
int count = 0;
for (int i = 0; (i < s0) && (i < s1); i++) //iterates through array adding sum until either size is met.
{
int sum = i0[i] + i1[i];
if (sum > 9)
{
count++;
}
i0[i] = sum;
}
int tmpSize = (!(s0>s1) ? s0 : s1) + count; //gets smaller index, adds count of sums > 9 (2 Digit)
int *tmp = new int[tmpSize]; //creates tmp dynamic array
int j = 0; //used to iterate through temp array
for (int i = 0; i < tmpSize; i++) // iterates through original array of sums
{
if (i0[i] > 9)
{
tmp[j] = i0[i]/10; //places tens place into array index
tmp[j + 1] = i0[i]%10; //places ones place into array index
j++; // adds 1 to array to account for 2 indexes being split
}
else
tmp[j] = i0[i];
j++;
}
s0 = tmpSize;
return i0; // returns final array
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication3
{
class Program
{
static void Main(string[] args)
{
int[] firstArray = { 9, 2, 9, 4 };
int[] secondArray = { 1, 2, 2, 5, 1 };
int[] resultArray = CalculateSum(firstArray, secondArray);
Console.Write("{");
resultArray.ToList().ForEach(w => Console.Write(w + ","));
Console.Write("}");
Console.ReadLine();
}
static int[] CalculateSum(int[] sourceA, int[] sourceB)
{
Stack<int> stack = new Stack<int>();
int maxArrayLength = Math.Max(sourceA.Length, sourceB.Length);
int lastIndex = 1;
bool carrySum = false;
int carryValue = 0;
while (lastIndex < (maxArrayLength + 1))
{
int sum = 0;
if (sourceA.Length - lastIndex >= 0)
{
sum += sourceA[sourceA.Length - lastIndex];
}
if (sourceB.Length - lastIndex >= 0)
{
sum += sourceB[sourceB.Length - lastIndex];
}
if (carrySum)
{
sum += carryValue;
}
if (sum > 9)
{
carrySum = true;
carryValue = (int)(sum / 10);
sum = (int)(sum % 10);
}
else
{
carrySum = false;
}
stack.Push(sum);
lastIndex++;
}
if (carrySum)
{
stack.Push(carryValue);
}
int[] finalArray = new int[stack.Count];
for (int i = 0; i < finalArray.Length; ++i)
{
finalArray[i] = stack.Pop();
}
return finalArray;
}
}
}
public int[] getSum(int[]a , int[]b ){
int n1 = a.length();
int n2 = b.length();
int i = n1-1;
int j = n2-2;
int max = Math.max(n1,n2)+1;
int[]res = new int[max];
int c = 0 ; int k = max-1;
while(i >= 0 && j >= 0 ){
int s = a[i]+b[j]+c;
if(s > 9){
c = 1; res[k--] = s%10;
}else{
c = 0 ;
res[k--] = s;
}
--i ; --j;
}
if( i >= 0 ){
while( i >= 0 ){
int s = a[i]+c;
if(s > 9){
c = 1; res[k--] = s%10;
}else{
c = 0 ;
res[k--] = s;
}
--i ;
}
}
if( j >= 0 ){
while( j >= 0 ){
int s = b[j]+c;
if(s > 9){
c = 1; res[k--] = s%10;
}else{
c = 0 ;
res[k--] = s;
}
--j ;
}
}
if(c > 0 ) res[0] = c;
return res;
JavaScript
const answer = (a, b) => {
const [ smaller, larger ] = a.length < b.length ? [ a, b ] : [ b, a ];
const diff = larger.length - smaller.length;
return larger.reduce((prev, cur, i) =>
(['' + prev[0] + cur, '' + prev[1] + (smaller[i - diff] ? smaller[i - diff] : 0) ])
, ['', '']
)
.reduce((prev, cur) => prev + +cur, 0)
.toString()
.split('')
.map(x => +x);
}
JavaScript
const answer = (a, b) => {
const [ smaller, larger ] = a.length < b.length ? [ a, b ] : [ b, a ];
const diff = larger.length - smaller.length;
return larger.reduce((prev, cur, i) =>
(['' + prev[0] + cur, '' + prev[1] + (smaller[i - diff] ? smaller[i - diff] : 0) ])
, ['', '']
)
.reduce((prev, cur) => prev + +cur, 0)
.toString()
.split('')
.map(x => +x);
}
a = [1,2,3]
b = [2,3,5,5]
# a=[9,9,2]
# b=[0,1,3]
a = a[::-1]
b = b[::-1]
lmin = min(len(a),len(b))
s=[0]
for x in range(lmin):
s[x] += a[x]+b[x]
s.append(s[x]/10)
s[x] = s[x]%10
for x in a[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
for x in b[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
print s[::-1]
a = [1,2,3]
b = [2,3,5,5]
# a=[9,9,2]
# b=[0,1,3]
a = a[::-1]
b = b[::-1]
lmin = min(len(a),len(b))
s=[0]
for x in range(lmin):
s[x] += a[x]+b[x]
s.append(s[x]/10)
s[x] = s[x]%10
for x in a[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
for x in b[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
print s[::-1]
a = [1,2,3]
b = [2,3,5,5]
# a=[9,9,2]
# b=[0,1,3]
a = a[::-1]
b = b[::-1]
lmin = min(len(a),len(b))
s=[0]
for x in range(lmin):
s[x] += a[x]+b[x]
s.append(s[x]/10)
s[x] = s[x]%10
for x in a[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
for x in b[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
print s[::-1]
a = [1,2,3]
b = [2,3,5,5]
# a=[9,9,2]
# b=[0,1,3]
a = a[::-1]
b = b[::-1]
lmin = min(len(a),len(b))
s=[0]
for x in range(lmin):
s[x] += a[x]+b[x]
s.append(s[x]/10)
s[x] = s[x]%10
for x in a[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
for x in b[lmin:]:
tmp = s[-1] + x
s[-1] += tmp%10
s.append(tmp/10)
print s[::-1]
Android:
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
resultValue = (TextView)findViewById(R.id.value);
input1Value = (TextView)findViewById(R.id.input1Value);
input2Value = (TextView)findViewById(R.id.input2Value);
ArrayList<Integer> A = new ArrayList<>();
A.add(9);
A.add(9);
A.add(4);
A.add(5);
ArrayList<Integer> B = new ArrayList<>();
B.add(6);
B.add(9);
B.add(6);
ArrayList<Integer> valueSet= getArraySum(A,B);
input1Value.setText(getArrayValuesAsString(A));
input2Value.setText(getArrayValuesAsString(B));
String valStr = "";
for (Integer i: valueSet
) {
valStr =","+ i.toString() + valStr;
}
if(!valStr.isEmpty()){
valStr = valStr.substring(1);
}
resultValue.setText(valStr);
}
public ArrayList<Integer> getArraySum(ArrayList<Integer> A, ArrayList<Integer> B){
ArrayList<Integer> sum = new ArrayList<>();
int lenA = A.size();
int lenB = B.size();
int currentA = lenA -1;
int currentB = lenB -1;
int carry = 0;
int currentSum = 0;
while (currentA >= 0 && currentB >= 0){
currentSum = A.get(currentA) + B.get(currentB)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentA--;
currentB--;
}
while (currentA >=0){
currentSum = A.get(currentA)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentA--;
}
while (currentB >=0){
currentSum = B.get(currentA)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentB--;
}
if(carry > 0){
sum.add(carry);
}
return sum;
}
private String getArrayValuesAsString(ArrayList<Integer> arr){
String str = "";
for (Integer i: arr) {
str =str+ i.toString() + ",";
}
return str;
}
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
resultValue = (TextView)findViewById(R.id.value);
input1Value = (TextView)findViewById(R.id.input1Value);
input2Value = (TextView)findViewById(R.id.input2Value);
ArrayList<Integer> A = new ArrayList<>();
A.add(9);
A.add(9);
A.add(4);
A.add(5);
ArrayList<Integer> B = new ArrayList<>();
B.add(6);
B.add(9);
B.add(6);
ArrayList<Integer> valueSet= getArraySum(A,B);
input1Value.setText(getArrayValuesAsString(A));
input2Value.setText(getArrayValuesAsString(B));
String valStr = "";
for (Integer i: valueSet
) {
valStr =","+ i.toString() + valStr;
}
if(!valStr.isEmpty()){
valStr = valStr.substring(1);
}
resultValue.setText(valStr);
}
public ArrayList<Integer> getArraySum(ArrayList<Integer> A, ArrayList<Integer> B){
ArrayList<Integer> sum = new ArrayList<>();
int lenA = A.size();
int lenB = B.size();
int currentA = lenA -1;
int currentB = lenB -1;
int carry = 0;
int currentSum = 0;
while (currentA >= 0 && currentB >= 0){
currentSum = A.get(currentA) + B.get(currentB)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentA--;
currentB--;
}
while (currentA >=0){
currentSum = A.get(currentA)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentA--;
}
while (currentB >=0){
currentSum = B.get(currentA)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentB--;
}
if(carry > 0){
sum.add(carry);
}
return sum;
}
private String getArrayValuesAsString(ArrayList<Integer> arr){
String str = "";
for (Integer i: arr) {
str =str+ i.toString() + ",";
}
return str;
}
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
resultValue = (TextView)findViewById(R.id.value);
input1Value = (TextView)findViewById(R.id.input1Value);
input2Value = (TextView)findViewById(R.id.input2Value);
ArrayList<Integer> A = new ArrayList<>();
A.add(9);
A.add(9);
A.add(4);
A.add(5);
ArrayList<Integer> B = new ArrayList<>();
B.add(6);
B.add(9);
B.add(6);
ArrayList<Integer> valueSet= getArraySum(A,B);
input1Value.setText(getArrayValuesAsString(A));
input2Value.setText(getArrayValuesAsString(B));
String valStr = "";
for (Integer i: valueSet
) {
valStr =","+ i.toString() + valStr;
}
if(!valStr.isEmpty()){
valStr = valStr.substring(1);
}
resultValue.setText(valStr);
}
public ArrayList<Integer> getArraySum(ArrayList<Integer> A, ArrayList<Integer> B){
ArrayList<Integer> sum = new ArrayList<>();
int lenA = A.size();
int lenB = B.size();
int currentA = lenA -1;
int currentB = lenB -1;
int carry = 0;
int currentSum = 0;
while (currentA >= 0 && currentB >= 0){
currentSum = A.get(currentA) + B.get(currentB)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentA--;
currentB--;
}
while (currentA >=0){
currentSum = A.get(currentA)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentA--;
}
while (currentB >=0){
currentSum = B.get(currentA)+carry;
if(currentSum > 9){
carry = currentSum /10;
currentSum = currentSum%10;
}else{
carry = 0;
}
sum.add(currentSum);
currentB--;
}
if(carry > 0){
sum.add(carry);
}
return sum;
}
private String getArrayValuesAsString(ArrayList<Integer> arr){
String str = "";
for (Integer i: arr) {
str =str+ i.toString() + ",";
}
return str;
}
public static int[] addArrays(int[] a, int[] b) {
// base cases: either is null, or one is empty array
if (a == null || b == null) {
return null;
}
if (a.length == 0) {
return b;
}
if (b.length == 0) {
return a;
}
// create result array 1 longer than longest of two inputs (in case of carry over)
int[] r = new int[Math.max(a.length, b.length) + 1];
// start at back of both arrays
int aInd = a.length - 1;
int bInd = b.length - 1;
while (aInd >= 0 || bInd >= 0) {
// target digit is max of aInd or bInd, +1 because of padding 0
int rInd = Math.max(aInd, bInd) + 1;
// add value of a digit and b digit only if the index is >= 0
r[rInd] += (aInd >= 0 ? a[aInd--] : 0);
r[rInd] += (bInd >= 0 ? b[bInd--] : 0);
//carry over to next digit
if (r[rInd] >= 10) {
r[rInd] -= 10;
r[rInd - 1]++;
}
}
// if leading digit is still 0, return slice from 1 to length
if (r[0] == 0) {
return Arrays.copyOfRange(r, 1, r.length);
}
return r;
}
int[] sumTwoArrays(int arr1[],int arr2[])
{
int resultArr[];
//Find the larger array and assign the result array size as one more than the larger array so as to accomodate the carry if any from the last digit of the larger array
if(arr1.length>arr2.length)
{
resultArr = new int[arr1.length+1];
}
else
{
resultArr = new int[arr2.length+1];
}
//Set iterators to last index of the respective arrays
int arr1Iterator=arr1.length-1;
int arr2Iterator=arr2.length-1;
int resultIterator=resultArr.length-1;
//Set inititial carry as zero
int carry=0;
//Start summing up from the last index and set the values in the respective positions of the result array.
//This while loop performs summation until any one of the array gets fully processed
while(arr1Iterator>=0 && arr2Iterator>=0)
{
resultArr[resultIterator] = carry+arr1[arr1Iterator]+arr2[arr2Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr1Iterator--;
arr2Iterator--;
}
// This while loop completes the summation of elements if arr1 is larger than arr2
while(arr1Iterator>=0)
{
resultArr[resultIterator] = carry+arr1[arr1Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr1Iterator--;
}
//// This while loop completes the summation of elements if arr2 is larger than arr1
while(arr2Iterator>=0)
{
resultArr[resultIterator] = carry+arr2[arr2Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr2Iterator--;
}
return resultArr;
}
int[] sumTwoArrays(int arr1[],int arr2[])
{
int resultArr[];
//Find the larger array and assign the result array size as one more than the larger array so as to accomodate the carry if any from the last digit of the larger array
if(arr1.length>arr2.length)
{
resultArr = new int[arr1.length+1];
}
else
{
resultArr = new int[arr2.length+1];
}
//Set iterators to last index of the respective arrays
int arr1Iterator=arr1.length-1;
int arr2Iterator=arr2.length-1;
int resultIterator=resultArr.length-1;
//Set inititial carry as zero
int carry=0;
//Start summing up from the last index and set the values in the respective positions of the result array.
//This while loop performs summation until any one of the array gets fully processed
while(arr1Iterator>=0 && arr2Iterator>=0)
{
resultArr[resultIterator] = carry+arr1[arr1Iterator]+arr2[arr2Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr1Iterator--;
arr2Iterator--;
}
// This while loop completes the summation of elements if arr1 is larger than arr2
while(arr1Iterator>=0)
{
resultArr[resultIterator] = carry+arr1[arr1Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr1Iterator--;
}
//// This while loop completes the summation of elements if arr2 is larger than arr1
while(arr2Iterator>=0)
{
resultArr[resultIterator] = carry+arr2[arr2Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr2Iterator--;
}
return resultArr;
}
int[] sumTwoArrays(int arr1[],int arr2[])
{
int resultArr[];
//Find the larger array and assign the result array size as one more than the larger array so as to accomodate the carry if any from the last digit of the larger array
if(arr1.length>arr2.length)
{
resultArr = new int[arr1.length+1];
}
else
{
resultArr = new int[arr2.length+1];
}
//Set iterators to last index of the respective arrays
int arr1Iterator=arr1.length-1;
int arr2Iterator=arr2.length-1;
int resultIterator=resultArr.length-1;
//Set inititial carry as zero
int carry=0;
//Start summing up from the last index and set the values in the respective positions of the result array.
//This while loop performs summation until any one of the array gets fully processed
while(arr1Iterator>=0 && arr2Iterator>=0)
{
resultArr[resultIterator] = carry+arr1[arr1Iterator]+arr2[arr2Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr1Iterator--;
arr2Iterator--;
}
// This while loop completes the summation of elements if arr1 is larger than arr2
while(arr1Iterator>=0)
{
resultArr[resultIterator] = carry+arr1[arr1Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr1Iterator--;
}
//// This while loop completes the summation of elements if arr2 is larger than arr1
while(arr2Iterator>=0)
{
resultArr[resultIterator] = carry+arr2[arr2Iterator];
carry=resultArr[resultIterator]/10;
resultArr[resultIterator] =resultArr[resultIterator]%10;
resultIterator--;
arr2Iterator--;
}
return resultArr;
}
def split_digits(num):
return [int(c) for c in str(num)]
def list_to_int(xs):
ls_of_str = (str(i) for i in xs)
return int(''.join(ls_of_str))
def array_sum(x, y):
return split_digits(list_to_int(x) + list_to_int(y))
assert list_to_int([1,2,3]) == 123
assert split_digits(12345) == [1,2,3,4,5]
assert array_sum([1,2,3], [2,3,4]) == [3,5,7]
assert array_sum([1,2,3], [2,3,5,5]) == [2,4,7,8]
assert array_sum([9,9,2], [0,1,3]) == [1,0,0,5]
import java.util.Arrays;
public class ArraySumElementWiseDemo {
public static void main(String[] args) {
int a[] = { 1, 2, 3 }, b[] = { 2, 3, 5, 5 };
System.out.println(Arrays.toString(sumArrays(a, b)));
}
public static int[] sumArrays(int a[], int b[]) {
long aValue = 0, bValue = 0;
int c[];
for (int i = 0; i < a.length; i++) {
aValue = aValue * 10 + a[i];
}
for (int i = 0; i < b.length; i++) {
bValue = bValue * 10 + b[i];
}
long cValueRev = 0, cValue = aValue + bValue;
int len = 0;
while (cValue > 0) {
cValueRev = cValueRev * 10 + cValue % 10;
cValue = cValue / 10;
len++;
}
c = new int[len];
for (int i = 0; i < len; i++) {
c[i] = (new Long(cValueRev % 10)).intValue();
cValueRev = cValueRev / 10;
}
return c;
}
}
import java.util.Arrays;
public class ArraySumElementWiseDemo {
public static void main(String[] args) {
int a[] = { 1, 2, 3 }, b[] = { 2, 3, 5, 5 };
System.out.println(Arrays.toString(sumArrays(a, b)));
}
public static int[] sumArrays(int a[], int b[]) {
long aValue = 0, bValue = 0;
int c[];
for (int i = 0; i < a.length; i++) {
aValue = aValue * 10 + a[i];
}
for (int i = 0; i < b.length; i++) {
bValue = bValue * 10 + b[i];
}
long cValueRev = 0, cValue = aValue + bValue;
int len = 0;
while (cValue > 0) {
cValueRev = cValueRev * 10 + cValue % 10;
cValue = cValue / 10;
len++;
}
c = new int[len];
for (int i = 0; i < len; i++) {
c[i] = (new Long(cValueRev % 10)).intValue();
cValueRev = cValueRev / 10;
}
return c;
}
}
import java.util.Arrays;
public class ArraySumElementWiseDemo {
public static void main(String[] args) {
int a[] = { 1, 2, 3 }, b[] = { 2, 3, 5, 5 };
System.out.println(Arrays.toString(sumArrays(a, b)));
}
public static int[] sumArrays(int a[], int b[]) {
long aValue = 0, bValue = 0;
int c[];
for (int i = 0; i < a.length; i++) {
aValue = aValue * 10 + a[i];
}
for (int i = 0; i < b.length; i++) {
bValue = bValue * 10 + b[i];
}
long cValueRev = 0, cValue = aValue + bValue;
int len = 0;
while (cValue > 0) {
cValueRev = cValueRev * 10 + cValue % 10;
cValue = cValue / 10;
len++;
}
c = new int[len];
for (int i = 0; i < len; i++) {
c[i] = (new Long(cValueRev % 10)).intValue();
cValueRev = cValueRev / 10;
}
return c;
}
}
public static void main(String[] args) { int[] a1 = new int[]{8, 9, 9, 9, 2}; int[] a2 = new int[]{4, 1, 0, 1, 3}; System.out.println(" sum " + sum(a1,a2)); } static List<Integer> sum(int[] a1, int[] a2) { List<Integer> sum = new ArrayList<>(); int carry = 0; int i = a1.length>a2.length?a1.length-1:a2.length-1; for (; i >= 0; i--) { int s1 = a1.length >= i ? a1[i] : 0; int s2 = a2.length >= i ? a2[i] : 0; int s = s1 + s2 + carry; sum.add(0, s % 10); carry = s / 10; } if(carry>0)sum.add(0, carry); return sum; }
C
// length of c is max(n, m)+1;
int add_digit_array(const int* a, const int n, const int* b, const int m, int* c) {
int i;
int carry = 0;
int sum;
if (!a || !b || !c || n < 1 || m < 1) return -1;
if (n > m) return add_digit_array(b, m, a, n, c);
for (i = 0; i < m; i++) {
sum = carry+b[m-1-i];
if (i < n) sum += a[n-1-i];
carry = sum > 9;
if (carry) sum -= 10;
c[m-i] = sum;
}
c[0] = carry;
return 0;
}
public class Add2Arrays
{
/**
* @param args
*/
int[] arr1 = new int[]{4,9,9,2};
int[] arr2 = new int[]{0,1,3};
public static void main(String[] args)
{
Add2Arrays obj = new Add2Arrays();
obj.add();
}
private void add()
{
ArrayList<Integer> result = new ArrayList<Integer>();
int p1 = this.arr1.length-1;
int p2 = this.arr2.length-1;
int carry = 0;
int v1 = 0;
int v2 = 0;
while(p1>=0 || p2>=0)
{
if(p1>=0)
v1 = this.arr1[p1];
if(p2>=0)
v2 = this.arr2[p2];
int sum = v1+v2+carry;
if(sum>=10)
{
sum = sum%10;
carry = 1;
}
else
{
carry = 0;
}
result.add(sum);
p2--;
p1--;
v1 = v2 = 0;
}
if(carry==1)
result.add(carry);
Collections.reverse(result);
System.out.println("Result is "+result);
}
}
public class Add2Arrays
{
/**
* @param args
*/
int[] arr1 = new int[]{4,9,9,2};
int[] arr2 = new int[]{0,1,3};
public static void main(String[] args)
{
Add2Arrays obj = new Add2Arrays();
obj.add();
}
private void add()
{
ArrayList<Integer> result = new ArrayList<Integer>();
int p1 = this.arr1.length-1;
int p2 = this.arr2.length-1;
int carry = 0;
int v1 = 0;
int v2 = 0;
while(p1>=0 || p2>=0)
{
if(p1>=0)
v1 = this.arr1[p1];
if(p2>=0)
v2 = this.arr2[p2];
int sum = v1+v2+carry;
if(sum>=10)
{
sum = sum%10;
carry = 1;
}
else
{
carry = 0;
}
result.add(sum);
p2--;
p1--;
v1 = v2 = 0;
}
if(carry==1)
result.add(carry);
Collections.reverse(result);
System.out.println("Result is "+result);
}
}
Can someone tell me whats wrong with this simple implementation ??
int[] arr1 = { 1, 2, 3 };
int[] arr2 = { 1, 2, 3 ,4, 5, 6};
int p = arr1.Count() + arr2.Count();
int[] arr3 = new int[p];
int i, j, k,carry = 0 ;
int l, q;
i = arr1.Count();
j = arr2.Count();
while (i > 0 || j > 0)
{
if (i <=0) l = 0;
else
l = arr1[i - 1];
if (j <= 0) q = 0;
else
q = arr2[j - 1];
k =l+q + carry;
if (k > 9)
{
arr3[p-1] = k % 10;
carry = k / 10;
}
else
{
arr3[p-1] = k;
carry = 0;
}
i--;
j--;
p--;
}
import java.util.ArrayList;
public static void main(String args[])
{
/*write a method that takes in 2 int arrays of any size and returns an array that calculates the sum of both.
for example, [1,2,3] and [2,3,4] will return [3,5,7]
Or [1,2,3] and [2,3,5,5] will return [2,4,7,8]
however, if it's like [9,9,2] and [0,1,3] you need to carry the sum so it returns as [1,0,0,5]
*/
int []a={1,2,3};
int []b={2,3,5,5};
int carry=0,sum=0;
ArrayList<Integer> arr= new ArrayList<Integer>();
for(int i=a.length-1,j=b.length-1;i>=0||j>=0;i--,j--)
{
if(i>=0 &&j>=0)
{
sum=a[i]+b[j]+carry;
carry= sum/10;
if(carry!=0)
arr.add(sum%10);
else
arr.add(sum);
}
else
{
if(j>=0)
{
sum=b[j]+carry;
carry= sum/10;
if(carry!=0)
arr.add(sum%10);
else
arr.add(sum);
}
else
{
sum=a[i]+carry;
carry= sum/10;
if(carry!=0)
arr.add(sum%10);
else
arr.add(sum);
}
}
}
if(carry>0)
arr.add(carry);
for(int i=arr.size()-1;i>=0;i--)
{
System.out.println(arr.get(i));
}
}
private static int[] ArraysSum(int[] a, int [] b)
{
if(a.length == 0 && b.length ==0)
return null;
else if(a.length == 0)
return b;
else if(b.length == 0) return a;
if (a.length > b.length)
return DoSum(a, b);
else
return DoSum(b,a);
}
private static int [] DoSum(int[] a, int [] b )
{
int m = a.length;
int n = b.length;
int r=0;
if(m > n ){
if(a[0] == 9 && m-n ==1 )
r=m+1;
else
r = m;
}
else
{
if(b[0] == 9 && n-m ==1)
r=n+1;
else
r = n;
}
int sum =0;
boolean carry = false ;
int [] c = new int [r];
for(int i = 1 ; i <= m ; i++ )
{
if(i <= n)
sum = a[m-i] + b[n-i];
else
sum = a[m-i];
if(carry)
{
sum = sum + 1;
carry = false;
}
if(sum > 9)
{
sum = sum%10;
carry = true;
}
c[c.length -i] = sum;
sum=0;
}
if(carry)
c[0] = 1;
return c;
}
object matchTwoArrays {
/**
* *
* write a method that takes in 2 int arrays of any size and returns
* an array that calculates the sum of both.
*
*
*/
def solution(a: Array[Int], b: Array[Int]): Array[Int] = {
// convert Int to Array of single digit Int. e.g 12 => Array(1,2)
val g = (x: Int) => x.toString.toCharArray.map(_.toInt - 48)
val sizediff = a.size - b.size
val zr0 = Array.fill(math.abs(sizediff)) { 0 }
val zipped = sizediff match {
case 0 => a zip b
case x if x > 0 =>
val zr1 = zr0 ++ b
a zip zr1
case x if x < 0 =>
val zr1 = zr0 ++ a
zr1 zip b
}
val res = zipped.map(x => x._1 + x._2)
res.flatMap(g(_))
}
solution(Array(1, 2, 3), Array(2, 3, 4)) //> res0: Array[Int] = Array(3, 5, 7)
solution(Array(2, 3, 5, 5), Array(1, 2, 3)) //> res1: Array[Int] = Array(2, 4, 7, 8)
solution(Array(9, 9, 2), Array(0, 1, 3)) //> v : Array[Int] = Array(9, 1, 0, 5)
}
Python3 here
def array_zip(array1, array2):
array1, array2 = sorted([array1, array2], key=len)
len_diff = len(array2)-len(array1)
if len_diff:
array1 = [0] * len_diff + array1
return zip(array1, array2)
def adder(array1, array2):
"""
>>> print(adder([7,7,7],[3,1,3]))
>>> deque([1, 0, 9, 0])
"""
pair_list = list(array_zip(array1, array2))
carry = 0
import collections
result = collections.deque()
for i,item in enumerate(reversed(pair_list), start=1):
pair_sum = sum(item)+carry
if pair_sum >= 10:
carry = 1
pair_sum-=10
else:
carry = 0
result.appendleft(pair_sum)
if carry == 1:
result.appendleft(1)
return result
public class sumOfDigitsArray {
public static void main(String args[]) {
int a[] = {1,9,2,8};
int b [] = {9,6,8,4};
ArrayList<Integer> result = new ArrayList<Integer>();
int k=0;
for(int i=0;i<a.length;i++){
int sum = a[i]+b[i];
int digits[] = new int[2];
if(sum>=10){
digits=convertNumberToDigits(sum);
result.add(digits[1]);
result.add(digits[0]);
}
else
result.add(sum);
}
for(int i = 0 ;i<result.size();i++){
System.out.print(result.get(i)+",");
}
}
public static int[] convertNumberToDigits(int x){
int result[] = new int[2];
int temp = x;
result[0]=x%10;
x=x/10;
result[1]=x%10;
return result;
}
Here's my C++ solution:
int main() {
int a[3], b[3], c[4], carry = 0, x;
cout << "Enter the arrays: ";
for (int i = 0; i < 3; i++)
cin >> a[i];
for (int i = 0; i < 3; i++)
cin >> b[i];
for (int i = 2; i >= 0; i--)
{
x = i - 1;
c[i+1] = a[i] + b[i] + carry;
if ( c[i+1] >= 10 && x >= -1 )
{
c[i+1] = c[i+1] - 10;
carry = 1;
}
else{
carry = 0;
}
}
if (carry == 1)
x = 0;
else x = 1;
for ( int i = x ; i<4; i++)
{
if (carry == 1)
c[0] = 1;
cout << c[i] << " ";
}
}
int[] a = {9,9,2};
int[] b = {0,1,3};
String aString = "";
String bString = "";
for(int i : a)
aString += i;
for(int i : b)
bString += i;
int aInt = Integer.parseInt(aString);
int bInt = Integer.parseInt(bString);
int sum = aInt + bInt;
String temp = Integer.toString(sum);
int[] newGuess = new int[temp.length()];
for (int i = 0; i < temp.length(); i++)
{
newGuess[i] = temp.charAt(i) - '0';
}
System.out.println(Arrays.toString(newGuess));
int[] a = {9,9,2};
int[] b = {0,1,3};
String aString = "";
String bString = "";
for(int i : a)
aString += i;
for(int i : b)
bString += i;
int aInt = Integer.parseInt(aString);
int bInt = Integer.parseInt(bString);
int sum = aInt + bInt;
String temp = Integer.toString(sum);
int[] newGuess = new int[temp.length()];
for (int i = 0; i < temp.length(); i++)
{
newGuess[i] = temp.charAt(i) - '0';
}
System.out.println(Arrays.toString(newGuess));
public static void main(String[] args) {
String str1 = "",str2="";
int arr1[]={9,9,8};
int arr2[]={7,1,9};
for(int i:arr1){
str1+= Integer.toString(i);
}
int a= Integer.parseInt(str1);
for(int i:arr2){
str2+= Integer.toString(i);
}
int b= Integer.parseInt(str2);
int x=a+b;
String str3=Integer.toString(x);
int k=0;
int arr3[];
if(arr2[0]>5||arr1[0]>5){
arr3= new int[arr2.length+1];
}
else{
arr3= new int[arr2.length];
}
for(int i=0;i<str3.length();i++){
arr3[k]=Character.getNumericValue(str3.charAt(i));
k++;
}
for(int i=0;i<arr3.length;i++){
System.out.println("arr3[k]....."+arr3[i]);
}
}
public static void main(String[] args) {
String str1 = "",str2="";
int arr1[]={9,9,8};
int arr2[]={7,1,9};
for(int i:arr1){
str1+= Integer.toString(i);
}
int a= Integer.parseInt(str1);
for(int i:arr2){
str2+= Integer.toString(i);
}
int b= Integer.parseInt(str2);
int x=a+b;
String str3=Integer.toString(x);
int k=0;
int arr3[];
if(arr2[0]>5||arr1[0]>5){
arr3= new int[arr2.length+1];
}
else{
arr3= new int[arr2.length];
}
for(int i=0;i<str3.length();i++){
arr3[k]=Character.getNumericValue(str3.charAt(i));
k++;
}
for(int i=0;i<arr3.length;i++){
System.out.println("arr3[k]....."+arr3[i]);
}
}
public static void main(String[] args) {
String str1 = "",str2="";
int arr1[]={9,9,8};
int arr2[]={7,1,9};
for(int i:arr1){
str1+= Integer.toString(i);
}
int a= Integer.parseInt(str1);
for(int i:arr2){
str2+= Integer.toString(i);
}
int b= Integer.parseInt(str2);
int x=a+b;
String str3=Integer.toString(x);
int k=0;
int arr3[];
if(arr2[0]>5||arr1[0]>5){
arr3= new int[arr2.length+1];
}
else{
arr3= new int[arr2.length];
}
for(int i=0;i<str3.length();i++){
arr3[k]=Character.getNumericValue(str3.charAt(i));
k++;
}
for(int i=0;i<arr3.length;i++){
System.out.println("arr3[k]....."+arr3[i]);
}
}
public static void main(String[] args) {
String str1 = "",str2="";
int arr1[]={9,9,8};
int arr2[]={7,1,9};
for(int i:arr1){
str1+= Integer.toString(i);
}
int a= Integer.parseInt(str1);
for(int i:arr2){
str2+= Integer.toString(i);
}
int b= Integer.parseInt(str2);
int x=a+b;
String str3=Integer.toString(x);
int k=0;
int arr3[];
if(arr2[0]>5||arr1[0]>5){
arr3= new int[arr2.length+1];
}
else{
arr3= new int[arr2.length];
}
for(int i=0;i<str3.length();i++){
arr3[k]=Character.getNumericValue(str3.charAt(i));
k++;
}
for(int i=0;i<arr3.length;i++){
System.out.println("arr3[k]....."+arr3[i]);
}
}
Code:
public static int[] sumArrays(int[] a, int[] b) {
int[] res = new int[Math.max(a.length, b.length) + 1];
int aIdx = a.length - 1;
int bIdx = b.length - 1;
int resIdx = res.length - 1;
int carry = 0;
while (aIdx >= 0 || bIdx >= 0) {
int sum = (aIdx >= 0 ? a[aIdx--] : 0) + (bIdx >= 0 ? b[bIdx--] : 0) + carry;
res[resIdx--] = sum % 10;
carry = sum / 10;
}
res[0] = carry;
return res;
}
JUnit:
@Test
public void test_sumArrays() {
int[] a = {3,5,7};
int[] b = {6,1,3,9};
int[] expected = {0,6,4,9,6};
Assert.assertArrayEquals(expected, InterviewQuestions.sumArrays(a, b));
int[] a1 = {9,9,9};
int[] b1 = {9,9,9,9};
int[] expected1 = {1,0,9,9,8};
Assert.assertArrayEquals(expected1, InterviewQuestions.sumArrays(a1, b1));
int[] a2 = {9,9,2};
int[] b2 = {0,1,3};
int[] expected2 = {1,0,0,5};
Assert.assertArrayEquals(expected2, InterviewQuestions.sumArrays(a2, b2));
}
Objective-C Solution
+ (NSArray *)sum:(NSArray *)num1 with:(NSArray *)num2
{
if (!num1.count) return num2;
if (!num2.count) return num1;
NSMutableArray *totalSum = [[NSMutableArray alloc] init];
int carryOver = 0;
int maxLength = MAX(num1.count, num2.count);
for (int x = 1; x <= maxLength; x++) {
int total = carryOver;
if ((int)num1.count - x >= 0) total = total + [num1[num1.count - x] intValue];
if ((int)num2.count - x >= 0) total = total + [num2[num2.count - x] intValue];
carryOver = total / 10;
int currNum = total % 10;
[totalSum insertObject:@(currNum) atIndex:0];
}
if (carryOver) {
[totalSum insertObject:@(carryOver) atIndex:0];
}
return [totalSum copy];
}
Soln 1 (beauty of python):
a = [1,2,3]
b = [2,3,5,5]
x = int(''.join(str(digit) for digit in a))
y = int(''.join(str(digit) for digit in b))
print (map(int,list(str(x+y))))
This has limitation might cause error if length of integer is greater than max length int can hold.
Soln 2: Overcomes previous limitaion
def findsum_aslist(a,b):
carry = 0
maxiter = max([len(a),len(b)])
list_sum = []
for i in range(maxiter):
x1 = 0
x2 = 0
if i<len(a):
x1 = a[-1-i]
if i<len(b):
x2 = b[-1-i]
y = x1+x2
list_sum.append(y%10)
carry = y//10
if i==maxiter-1 and carry!=0:
list_sum.append(carry)
return list_sum
a = [1,2,3]
b = [2,3,5,5]
list_sum = findsum_aslist(a,b)
print('['),
print(','.join(str(list_sum[-1-i]) for i in range(len(list_sum)))),
print(']')
public static int Calculate(List<int> li, List<int> li2)
{
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
for (int i = 0; i < li.Count; i++)
{
sb1.Append(li[i].ToString());
}
for (int j = 0; j < li.Count; j++)
{
sb2.Append(li2[j].ToString());
}
return Convert.ToInt32(sb1.ToString()) + Convert.ToInt32(sb2.ToString());
}
public static int Calculate(List<int> li, List<int> li2)
{
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
for (int i = 0; i < li.Count; i++)
{
sb1.Append(li[i].ToString());
}
for (int j = 0; j < li.Count; j++)
{
sb2.Append(li2[j].ToString());
}
return Convert.ToInt32(sb1.ToString()) + Convert.ToInt32(sb2.ToString());
}
Here's my code without having to loop through both arrays and checking for carry over number in c#:
int[] arr1 = { 1, 2, 3 };
int[] arr2 = { 2, 3, 5, 5 };
string a1 = String.Join("", arr1);
string a2 = String.Join("", arr2);
String sum = Convert.ToString(long.Parse(a1) + long.Parse(a2));
int[] result = sum.Select(x => Int32.Parse(x.ToString())).ToArray();
Here is the Java code for that:
- navidcs November 27, 2015public static int[] sumArrays(int[] a, int[] b) { if (a.length <= b.length) { return sumArraysFirstSmallerOrEqual(a, b); } else { return sumArraysFirstSmallerOrEqual(b, a); } } public static int[] sumArraysFirstSmallerOrEqual(int[] a, int[] b) { int[] result = new int[b.length + 1]; result[0] = 0; boolean moreThanNine = false; for (int i = 1; i <= b.length; ++i) { if (i <= a.length) { result[result.length - i] = a[a.length - i] + b[b.length - i]; } else { result[result.length - i] = b[b.length - i]; } if (moreThanNine) { ++result[result.length - i]; moreThanNine = false; } if (result[result.length - i] > 9) { result[result.length - i] -= 10; moreThanNine = true; } } if (moreThanNine) result[0] = 1; return result; }