Adding all elements of an array except the element at index with O(n) complexity

Question

This is what i came thru a problem in some coding test.

problem statement was like that we have to add all the elements of an array except the element at the index. subtraction operator cannot be used here and complexity should be O(n).

like arr={3,7,8,4,9} then result array will be... sum={28,24,23,27,22}

i have think a lot over it. but still missing something. some hint or pseudo code will be appreciable.

Concluded: if there is not any other reasonable answer to this then achieving subtraction by any mean could be possible solution. i have concluded it with using -1*arr[i] or complexity will be O(n2).

Edit: Above conclusion is not correct.

Answer 1

A simple O(n) approach that uses only addition (and no "cheats" like -1*elem or ~elem + 1 to simulate subtraction) is to do two passes:

• Create the result array sum.

• In a "forward" pass from index 0 to index n?1, set each element of sum to the sum of all "previous" elements in arr:

  int sumOfAllPrevious = 0;
  for (int i = 0; i < n; ++i) {
    sum[i] = sumOfAllPrevious;
    sumOfAllPrevious += arr[i];
  }
  

• In a "reverse" pass from index n?1 to index 0, augment each element of sum with the sum of all "later" elements in arr:

  int sumOfAllLater = 0;
  for (int i = n - 1; i >= 0; --i) {
    sum[i] += sumOfAllLater;
    sumOfAllLater += arr[i];
  }
  

Answer 2

Since the complexity of O(2n) = O(n), you can use one loop to calculate the entire sum. Then a second loop after wards and set the value at the index as arr[i] = totalSum-arr[i]

Edit: woops, did forget that you can't use subtraction. But hey, subtraction is equivalent to an addition with the two's complement, LOL.

Edit: Here is the solution in python2

arr = [3,7,8,4,9]
sum = 0
for elem in arr:
    sum += elem

for i in xrange(len(arr)):
    elem = arr[i]
    elem = ~elem + 1
    arr[i] = sum + elem

print arr

Output

./bla.py 
[28, 24, 23, 27, 22]

Answer 3

package assignments;

import java.util.Arrays;
import java.util.Scanner;

public class sumOfArrayExceptItself {

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n,i,j, sum=0,m=0;
        n=sc.nextInt();
        int arr[]=new int[n];
        int arr1[]=new int[n];
        for (i=0;i<n;i++) {
            arr[i]=sc.nextInt();
        }
        for(i=0;i<n;i++) {
            for(j=0;j<n;j++) {
                sum=sum+arr[j];
            }
            int a = sum-arr[i];
            arr1[i]=a;
            sum=0;
        }
        System.out.println(Arrays.toString(arr1).replace("[", " ").replace("]", " ").replace(","," "));
    }

}