## Interview Question

**Country:**United States

I would like to check if the value 19 should be printed.

For 3 it's pos 0 so 3 + 0 (i = 0)

For 6 it's pos 1 so 6 + value in next [1+1] = 8

For 2 it's pos 2 so 2 + values in next 2 = 18

For 7 it's pos 3 so 7 + the values in the next 3 values = 25

For 9 it's pos 4 and if we continue the pattern it's 9 + the next 4 values but there are only 3, since the example doesn't continue for 5,4,1, it's unclear if you just add to the end if you have less than i left to the end of the array

```
public static void main(String[] args) {
// test array
int[] array = {3, 6, 2, 7, 9, 5, 4, 1};
// list for result
List<Integer> result = new ArrayList<>();
for (int i = 0; i < array.length; i++) {
int sum = 0;
// sum element on i-th place + j (where j is 0, +1, +2 until i-th place.)
for (int j = 0; j <= i; j++) {
// stop when no numbers left
if (j+i >= array.length) {
break;
}
sum += array[j+i];
}
result.add(sum);
// condition to not overlap original array
if(2 * result.size() > array.length) {
break;
}
}
System.out.println(Arrays.toString(result.toArray()));
}
```

public static void main(String[] args) {

int[] nums = { 3, 6, 2, 7, 9, 5, 4, 1 };

boolean cont = true;

for (int i = 0, k = 0; i < nums.length; i++, k++) {

if (cont) {

int sum = nums[i];

for (int j = i; j < (k + i); j++) {

if ((j + 1) < nums.length) {

sum += nums[j + 1];

} else {

cont = false;

}

}

System.out.println(sum);

}

}

}

```
public static void main(String[] args) {
int[] nums = { 3, 6, 2, 7, 9, 5, 4, 1 };
boolean cont = true;
for (int i = 0, k = 0; i < nums.length; i++, k++) {
if (cont) {
int sum = nums[i];
for (int j = i; j < (k + i); j++) {
if ((j + 1) < nums.length) {
sum += nums[j + 1];
} else {
cont = false;
}
}
System.out.println(sum);
}
}
}
```

All the solutions above are O(N^2). This one is O(N):

```
def calc_sum_i(arr_in):
arr_len = len(arr_in)
arr_out = [0] * arr_len
# sum(i) = arr_in[i] + sum(i+1) - arr_in[2*i+1] - arr_in[2*i+2]
for i in range(arr_len-1, -1, -1):
sum_i = arr_in[i]
if i < arr_len-1:
sum_i += arr_out[i+1]
if 2*i+1 <= arr_len-1:
sum_i -= arr[2*i+1]
if 2*i+2 <= arr_len-1:
print("2*i+2")
sum_i -= arr[2*i+2]
arr_out[i] = sum_i
return arr_out
```

An O(N) algorithm:

```
def calc_sum_i(arr_in):
arr_len = len(arr_in)
arr_out = [0] * arr_len
# sum(i) = arr_in[i] + sum(i+1) - arr_in[2*i+1] - arr_in[2*i+2]
for i in range(arr_len-1, -1, -1):
sum_i = arr_in[i]
if i < arr_len-1:
sum_i += arr_out[i+1]
if 2*i+1 <= arr_len-1:
sum_i -= arr[2*i+1]
if 2*i+2 <= arr_len-1:
print("2*i+2")
sum_i -= arr[2*i+2]
arr_out[i] = sum_i
return arr_out
```

An O(N) solution:

```
def calc_sum_i(arr_in):
arr_len = len(arr_in)
arr_out = [0] * arr_len
# sum(i) = arr_in[i] + sum(i+1) - arr_in[2*i+1] - arr_in[2*i+2]
for i in range(arr_len-1, -1, -1):
sum_i = arr_in[i]
if i < arr_len-1:
sum_i += arr_out[i+1]
if 2*i+1 <= arr_len-1:
sum_i -= arr[2*i+1]
if 2*i+2 <= arr_len-1:
sum_i -= arr[2*i+2]
arr_out[i] = sum_i
return arr_out
```

Got a python3 solution here. Took under 30 minutes to make

- Kidus Michael February 06, 2021