• 4

Country: United States

Comment hidden because of low score. Click to expand.
13
of 13 vote

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:

``````from random import randint

a = []
for i in xrange(randint(5,10), randint(50,60)):
a.append(randint(1,100))

res = [0] * len(a)

sm = a[0]

for i in xrange(1, len(res)):
res[i] = sm
sm += a[i]

sm = a[len(a)-1]
for i in xrange(len(res)-2, -1, -1):
res[i] += sm
sm += a[i]

print sum(a)
print a
print res``````

Comment hidden because of low score. Click to expand.
0

This is the best solution. O(n) in time and O(1) in space.

Comment hidden because of low score. Click to expand.
0

That's awesome. Great solution!

Comment hidden because of low score. Click to expand.
0

``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?``

Comment hidden because of low score. Click to expand.
1
of 1 vote

java

``````public static int[] sumArray (int[] a) {
int[] res = new int[a.length];

int sum=a[0];
res[0]=0;
for (int i=1; i<a.length;i++) {
res[i]=sum;
sum+=a[i];
}

sum=a[a.length-1];
for (int i=a.length-2;i>=0;i--) {
res[i]+=sum;
sum+=a[i];
}
return res;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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].

Comment hidden because of low score. Click to expand.
0

Although this does consume O(N) space, so maybe someone can optimize this to use O(1) space?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

Nice solution! :) Can't think of O(1) space though...

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public static int[] arrayOfSum(int[] a) {
int sum=0;
int [] arraySum = new int[a.length];

for (int i = 0; i < a.length; i++) {
arraySum[i] = sum;
sum+=a[i];
}
sum=0;
for (int i = a.length-1; i >= 0; i--) {
arraySum[i] += sum;
sum+= a[i];
}

return arraySum;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

You cannot subtract. Read the question...But yes, that is the obvious solution if you could subtract.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a C++ solution that runs in O(n) time and uses O(n) space but can be easily modified to use O(1) space

``````int* solution(int* a, const int& asize){
int* b=new int[asize];

int sum=0;
for(int i=0;i<asize;++i){
sum+=a[i];
}
for( int i=0;i<asize,++i){
b[i]=sum+(~a[i])+1;
}
return b;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

O(1) space ?

Comment hidden because of low score. Click to expand.
0

Yes it is O(1) space as you have to return a different array not the same one, so this much space is needed indeed and O(n) performance

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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];
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

arr = [1,2,3,4]
sum = 10

it fails on the first element arr[0] XOR sum = 11 not 9, so this solution does not work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]+" ");
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Following code does not uses "-" sign

/**
* @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]+" ");
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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");
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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]);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]+" ");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

Comment hidden because of low score. Click to expand.
0

This is of the order o(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Haskell code: O(n) time O(1) space

``````q2 l = zipWith (+) dp1 dp2
where
dp1 = init \$ scanl (+) 0 l
dp2 = tail \$ scanr (+) 0 l``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

Comment hidden because of low score. Click to expand.
0

It specifically says that you cannot use the "-" operator so this solution is not valid!

Comment hidden because of low score. Click to expand.
0

without using "-" operator, 57 + (-1 *5) = 52 . Here "-" is sign, not operator :) . So this answer will become absolutely valid (by hacking the question)

Comment hidden because of low score. Click to expand.
0

lol, good luck getting past the google interview by "hacking" questions :)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.