Google Interview Question
Country: United States
You are given an array of integers 'a' that can fit in a memory. Does this mean you can use extra array. Shouldnt it be done in place?
Maintain two arrays (in the case of 4 elements for the input array):
{ 0, a[0], a[0]+a[1], a[0]+a[1]+a[2] }
{ a[1]+a[2]+a[3], a[2]+a[3], a[3], 0 }
Now add the arrays element by element (example: arr1[0] + arr2[0] etc...) into a new array and we get:
{a[1]+a[2]+a[3], a[0]+a[2]+a[3], a[0]+a[1]+a[3], a[0]+a[1]+a[2]}
The resulting array is the sum of all elements except a[i].
Although this does consume O(N) space, so maybe someone can optimize this to use O(1) space?
Nice solution! My Java implementation
public static int[] sum(int[] arr){
if (arr.length == 0)
return new int[0];
int[] arr1 = new int[arr.length];
int[] arr2 = new int[arr.length];
for (int i = 1 ; i < arr.length ; i++){
arr1[i] = arr1[i-1] + arr[i-1];
}
for (int i = arr.length-2 ; i >= 0 ; i--){
arr2[i] = arr2[i+1] + arr[i+1];
}
for (int i = 0 ; i < arr.length; i++){
arr1[i] += arr2[i];
}
return arr1;
}
I was thinking of the following idea...will test this with code a bit later. The idea is to use recursion. Lets say we have a three element arr a[] = {1, 2, 3}
Keep a running sum of path encountered until now..
if not last element in the array, recurse
if last element in array, store the running sum into array location AND start a running sum of the values from the bottom. The value at each index is the sum of running sum from top and running sum from bottom.
This will do this with only one array
Nice question. My solution is to implment a subtract(a, b) function that actually does a-b without using the '-' operator. If the language is Java or C++, we can use bit manipulation based on the fact that negative number is the 2-complement of the positive counter part.
subtract(a, b) can be implemented as a + opposite(b).
If b is positive than opposite(b) is obtained by flipping b (xor with 1<<32 for int) and adding 1. If b is negative than opposite(b) is obtained by SUBTRACTING 1 and flipping it (xor with 1<<32).
Now for how to subtracting 1 from a number without using '-'. We keep iterating from the least significant bit to the most significant bit, invert the bit until the last inverted bit was 1.
Personally I think the dynamic programming solution is more intuitive and more language-agnostic.
nice solution by @xiejilin@limijiaoyin.com
I have 1 more idea for the problem :
1. O(n) - add all numbers ; let total sum = Sum
2. while loop over all elements, subtract current element (a[i]) from sum
for( i = 0 ; i < n ; i++){
a[i] = Sum +(~a[i] +1); /* (~a[i] +1) is a[i]'s 2's complement */
}
hence over all complexity : O(n)
int* sumExcept(int[] arr, int size) {
int* result = new int[size];
int sum = 0;
memset(result, 0, sizeof(int) * size);
sum = arr[0];
for(int i = 1; i < size; ++i) {
result[i] = sum;
sum += arr[i]
}
sum = arr[n-1];
for (int i = size - 2; i >= 0; --i) {
result[i] += sum;
sum += arr[i];
}
return result;
}
public static int[] sumExcluding(int[] array)
{
if (array == null)
{
throw new IllegalArgumentException("array must not be null");
}
int[] sums = new int[array.length];
populateSumAfter(sums, array, 0);
int s = array[0];
for (int i = 1; i < sums.length; i++)
{
sums[i] += s;
s += array[i];
}
return sums;
}
private static int populateSumAfter(int[] sum, int[] array, int i)
{
if (i >= sum.length)
{
return 0;
}
else
{
sum[i] = populateSumAfter(sum, array, i + 1);
return sum[i] + array[i];
}
}
Wouldnt XOR work here?
1) Read the whole array once and calculate the sum
2) Create a new array where result[i] = sum XOR a[i]
I think this might work
O(n) both time and O(n) space.
Following code does not use "-" sign
public class ArrayAdd {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr={5,10,15,20,7};
print(arr);
}
private static void print(int[] arr) {
int sum=0,start=0,end=0;
int[] temp = new int[arr.length];
for(int i=0 ;i<arr.length;i++){
// System.out.println("i "+i+"arr length"+arr.length);
start=0;
sum=0;
end=i+1;
while(start < i)
{
sum+=arr[start];
start++;
}
// System.out.println("sum after start" + sum);
while(end != (arr.length))
{
sum+=arr[end];
end++;
}
// System.out.println("sum after end" + sum);
temp[i]=sum;
}
for(int i=0;i<temp.length;i++)
{
System.out.print(temp[i]+" ");
}
}
}
Following code does not uses "-" sign
public class ArrayAdd {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] arr={5,10,15,20,7};
print(arr);
}
private static void print(int[] arr) {
int sum=0,start=0,end=0;
int[] temp = new int[arr.length];
for(int i=0 ;i<arr.length;i++){
// System.out.println("i "+i+"arr length"+arr.length);
start=0;
sum=0;
end=i+1;
while(start < i)
{
sum+=arr[start];
start++;
}
// System.out.println("sum after start" + sum);
while(end != (arr.length))
{
sum+=arr[end];
end++;
}
// System.out.println("sum after end" + sum);
temp[i]=sum;
}
for(int i=0;i<temp.length;i++)
{
System.out.print(temp[i]+" ");
}
}
}
public class ArraySum {
public static void main(String[] args) {
int a[] = {0,1,2,3,4,5,6,7};
int ans[] = getArraySum(a);
for(int i : ans)
System.out.println(i);
//System.out.println(twosComplementSum(50,-1));
}
public static int [] getArraySum(int [] arr){
if(arr==null || arr.length==0)
return arr;
int ans[] = new int [arr.length];
int sum=0;
for(int i: arr)
sum+=i;
for(int i=0; i<arr.length; i++){
ans[i] = twosComplementSum(sum, arr[i]);
}
return ans;
}
public static int twosComplementSum(int sum, int num){
return 1 + sum + ((~1+1)^num);
}
public static int twosComplementSum2(int sum, int num){
for(int i=0;i<32;i++){
num = num ^ (1<<i);
}
sum = sum + num + 1;
return sum;
}
}
This implementation works. However it has a time complexity of n^2.
public static int[] addExcept(int[] test){
int[] array = new int[test.length];
for(int i= 0; i < test.length ; i++){
int total = 0;
for(int k=0; k< test.length; k++){
if(k != i ){
total += test[k];
}
}
array[i] = total;
}
return array;
}
int[] GetSum(int[] a)
{
int[] sumArray = new int[a.Length];
int sum = 0;
for (int i = 1; i < a.Length; i++)
{
sum = sum + a[i - 1];
sumArray[i] = sumArray[i - 1] + a[i - 1];
}
sum = 0;
for (int i = a.Length - 2; i >= 0; i--)
{
sum = sum + a[i + 1];
sumArray[i] = sum;
}
return sumArray;
}
#include<stdio.h>
void convert(int a[], int n);
int main() {
int a[] = {1,2,3,4,5,6,7,8};
convert(a,sizeof(a)/sizeof(int));
}
void convert(int a[], int n) {
int left=a[0];
a[0]=0;
for(int i=1;i<n;i++) {
int temp=a[i];
a[i]=left;
left+=temp;
}
int sum=left, right=0;
for(int i=n-1;i>=1;i--) {
int temp=sum-a[i];
sum=a[i];
a[i]+=right;
right+=temp;
}
a[0]+=right;
for(int i=0;i<n;i++) {
printf("%d ",a[i]);
}
printf("\n");
}
The code below has complexity O(n)
Main idea is to first get the sum of the entire array.Then traverse the entire array and and each element = sum + Not(element at that position +1)
public class IntArray{
public static void main(String args[]){
int arr[] ={5,7,2,9,3,1,6};
getArr(arr);
}
public static void getArr(int []arr){
int sum = 0;
for(int i =0;i<arr.length;i++)
sum += arr[i];
for(int i =0;i<arr.length;i++)
arr[i] = sum + ~arr[i] +1;
for(int i =0;i<arr.length;i++)
System.out.println(arr[i]);
}
}
you can code it as a recursion function because both of arrays fit in memory
public static int sumArray(int[] a, int[] b, int i, int preSum) {
if (i >= a.length) {
return 0;
}
int postSum = sumArray(a, b, i + 1, preSum + a[i]);
b[i] = preSum + postSum;
// System.out.println(i+","+b[i]);
return a[i] + postSum;
}
It is only mentioned to not use '-'. Using 2 complement's is a nice solution I can think of.
public class SumExcept {
public static void main(String args[]) {
Scanner s = new Scanner(System.in);
int n=s.nextInt(),arr[]=new int[n], sum=0;
for(int i=0; i<n; i++)
sum+=(arr[i]=s.nextInt());
for(int i=0;i<n;i++)
arr[i] = sum + ~arr[i]+1;
for(int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}
}
void generateNegateSumArray(std::vector<int> &a, std::vector<int> &b, int length)
{
int totalSum = 0;
b.reserve(length);
for(int i = 0; i < length; i++)
{
b[i] = a[i] * -1;
totalSum += a[i];
}
for(int i = 0; i < length; i++)
{
b[i] += totalSum;
}
}
The question asked not to use '-' OPERATOR. We can still multiply by -1 to subtract with using '-' operator.
two ways of solving it:
The first is iterative and has a worst case of o(n^2)
void func(int[] buff) {
int before, after = 0;
for(int i=0; i<buff.length; i++) {
for(int j=i+1; j<buff.length; j++) {
after += buff[j];
}
int tmp = buff[i];
buff[i] = before + after;
before += tmp;
after = 0;
}
}
Second option is recursive and has a runtime of o(n)
int func(int before, int index, int[] buff) {
if(index >= buff.length) return 0;
int after = func(before + buff[index], index+1, buff);
buff[index] = before + after;
return after+buff[index];
}
assume array is {5,10,15,20,7}
the sum of the elements is = 57
so the result is {57-5, 57-10,57-15,57-20,57-7}, so {52,47,42,37,50}
two for-loop of initial array needed (first to find the sum, other to update)
It specifically says that you cannot use the "-" operator so this solution is not valid!
without using "-" operator, 57 + (-1 *5) = 52 . Here "-" is sign, not operator :) . So this answer will become absolutely valid (by hacking the question)
I get an idea:
first , fill the new array like this:
arr[i] = sum(a[0,i-1])
This can be done in O(n) in a for loop
Then, reversely do the operation, and add result to the previous arr.
I'll try program this out,, but have to say,, always easier to think than do it for me..
Simple code:
- jilinxie1988@gmail.com January 13, 2015