Got stuck on quite simple problem in my code. I need to count what I would call a nested sums of an array. Let’s take as an example the array:
[1,2,2,3,6]
I want to sum them as:
0 + 1 = 1
1 + 2 = 3
1 + 2 + 2 = 5
1 + 2 + 2 + 3 = 8
1 + 2 + 2 + 3 + 6 = 14
sum = 1 + 3 + 5 + 8 + 14 = 31
Edit:
I tried to do it with stack, but it failed
int sums = 0;
Stack<int> sum = new Stack<int>();
for (int i = 0; i < queries.Length; i++)
{
sum.Push(queries[i]);
}
for (int i = 0; sum.Count != 0; i++)
{
if(i != 0)
{
sums += sum.Pop();
}
}
>Solution :
You can do this much more efficiently and more easily, by multiplying each value by its reversed index + 1
For example, using LINQ
int[] arr = { 1, 2, 2, 3, 6 };
var result = arr.Reverse().Select((val, i) => val * (i + 1)).Sum();
Note that .Reverse on an array (or other Collection<T>) does not actually move any items, it just reads them backwards. So this is therefore an O(n) operation, as opposed to your original solution which is O(n2 / 2)
You can also do this procedurally, this is almost the same as @aminrd’s answer.
int[] arr = { 1, 2, 2, 3, 6 };
var result = 0;
for (var i = arr.Length - 1; i >= 0; i--)
result += arr[i] * (i + 1);