Monday, 19 August 2013

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

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

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, 19, 18, 13}
I answered an obvious solution:
First evaluate sum of all numbers then subtract each element from sum. So
in above list sum is 2 + 7 + 1 + 3 + 8 = 21 then so like:
{sum - 2, sum - 7, sum - 1, sum - 3, sum - 8}
{21 - 2, 21 - 7, 21 - 1, 21 - 3, 21 - 8}
== {19, 14, 19, 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).

No comments:

Post a Comment