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


i asked:

replace each number in list sum of remaining elements, list not sorted.
suppose if have list of numbers {2, 7, 1, 3, 8}, replace each element sum of rest of elements. 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 obvious solution:
first evaluate sum of numbers subtract each element sum. above list sum 2 + 7 + 1 + 3 + 8 = 21, output 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 2 iterations of list.

then interviewer asked me: without subtraction? , couldn't answer :(

is other solution possible? can share other trick? better trick possible?

lets memory space can used (i asked after few minutes of try, couldn't answer).

one possibility compute prefix , suffix sums of array , combine appropriate entries. still o(n) needs more memory space think original method better.

in other words, {2, 7, 1, 3, 8} compute {2, 2+7, 2+7+1, 2+7+1+3, 2+7+1+3+8} , {2+7+1+3+8, 7+1+3+8, 1+3+8, 3+8, 8} , add appropriate entries.


Comments

Popular posts from this blog

Detect support for Shoutcast ICY MP3 without navigator.userAgent in Firefox? -

web - SVG not rendering properly in Firefox -

java - JavaFX 2 slider labelFormatter not being used -