Replace number by sum of other numbers in a list without subtraction

Question

I was asked:

Replace each number in a list by sum of remaining elements, the list is not sorted.
So suppose if we have a list of numbers like {2, 7, 1, 3, 8}, now we are to replace each element with sum of rest of elements. The output should be:

    {(7 + 1 + 3 + 8), (2 + 1 + 3 + 8), (2 + 7 + 3 + 8), (2 + 7 + 1 + 8), (2 + 7 + 1 + 3)}
==  {19, 14, 20, 18, 13}

I answered an obvious solution:
First evaluate sum of all numbers then subtract each element from sum. So for above list sum is 2 + 7 + 1 + 3 + 8 = 21, then for output do like:

    {sum - 2, sum - 7, sum - 1, sum - 3, sum - 8}
    {21 - 2, 21 - 7, 21 - 1, 21 - 3, 21 - 8}
==  {19, 14, 20, 18, 13}

It needs only two iterations of list.

Then Interviewer asked me: Now do it without subtraction? and I couldn't answer :(

Is other solution possible? Can some share any other trick? A better trick is possible?

Lets extra memory space can be used (I asked after a few minutes of try, even then I couldn't answer).

Answer 1

One possibility would be to compute prefix and suffix sums of your array and then combine the appropriate entries. This would still be O(n) but needs more memory space so I think your original method is better.

In other words, from {2, 7, 1, 3, 8} compute {2, 2+7, 2+7+1, 2+7+1+3, 2+7+1+3+8} and {2+7+1+3+8, 7+1+3+8, 1+3+8, 3+8, 8} and then add the appropriate entries.

Answer 2

The solution is to sum everything but the element. Then you don't have to subtract after the fact. You just skip adding the element at the current index.

Alternatively, you could get a subset of the list that excludes the element at the current index, then just sum the subset together. Pretty much the same thing as my first suggestion with more implementation detail.

Answer 3

C++ implementation. O(n) and done by keeping sums of all elements before and after a certain index.

#include <iostream>

int main() {
    int a[] = {2,7,1,3,8};

    int prefix[5]; // Sum of all values before current index
    int suffix[5]; // Sum of all values after current index

    prefix[0] = 0; 
    suffix[4] = 0; 

    for(int i = 1; i < 5; i++) {
        prefix[i] = prefix[i-1] + a[i-1];
        suffix[4 - i] = suffix[4 - i + 1] + a[4 - i + 1]; 
    }   

    // Print result
    for (int i = 0; i < 5; i++) {
        std::cout << prefix[i] + suffix[i] << " ";
    }   
    std::cout << std::endl;
}

Answer 4

I can't think anything better than yours.

But how about this :

Create a (n-1)xn matrix:

[ 2, 7, 1, 3, 8 ]

| 7, 1, 3, 8, 2 |  rotate by 1
| 1, 3, 8, 2, 7 |         by 2
| 3, 8, 2, 7, 1 |         by 3
| 8, 2, 7, 1, 3 |         by 4

Then Sum up the columns

C++'s std::rotate_copy can be used to create matrix

  std::vector<int> v1 {2, 7, 1, 3, 8 };
  std::vector<int> v2 (v1.size());
  int i,j;

  std::vector< std::vector<int> > mat;  
  for (int i=1; i<v1.size();++i){
     std::rotate_copy(v1.begin(),v1.begin()+i,v1.end(),v2.begin());
     mat.push_back(v2);
    }                                            

  for(j=0;j<v1.size();++j)  
    for(i=0;i<v1.size()-2;++i)
       v2[j]+=mat[i][j];

 for(i=0;i<v2.size();++i)
  std::cout<<v2[i]<<" ";

Answer 5

#include <iostream.h>
#include <stdio.h>

int main() {
    int a[] = {2,7,1,3,8};

    int sum[5]={0};


     for(int j = 0; j < 5; j++){
       for(int i = 1; i < 5; i++) {
        sum[j]=sum[j]+a[(j+i+5)%5];
        }
      printf("%d ", sum[j]);  }
}

Answer 6

Instead of subtracting the element you can add the element multiplied by -1. Multiplication and addition are allowed operations, I guess.