# HackerRank Coding Interview 6. Prefix Scores

4 min readDec 8, 2022

**Time to complete **— 30 minutes

**Question Type =** Medium

**Asked in = Microsoft, Uber, Lyft, Bloomberg, Morgan Stanley, Apple, and Google.**

**Skills:** arrays, sorting, greedy algorithm, prefix array

**Insights — **It should be read very carefully read and you must ask questions in between.

**Question —**

For any array of positive integers *a[a[1]..a[k]], *its *score(a)* is calculated as follows:

- For each
*a[i]*where*1 ≤ i ≤ k*in order, add the current maximum element in the array to*a[i]*. *score(a[k])*is the sum of the final elements in*a.*Since the sums may become large,*score(a)*should be calculated modulo (10*⁹ +7).*

## Example

*arr = [1, 2, 3]*

Since there are* 3* elements in *arr, k* will range from *1* to *3.*

`current new `

k i arr[1:k] max a score(a)

- - -------- ------- ------- -------

1 1 [1] 1 [2] 2

2 1 [1,2] 2 [3,2]

2 3 [3,5] 83 1 [1,2,3] 3 [4,2,3]

2 4 [4,6,3]

3 6 [4,6,9] 19

- In the first iteration,
*k = 1.*The array to consider,*a[]*=*arr[1:k] = [1]*. The maximum value in the array is*1*. Add*1*to*a[1] = 1*so*a’ = [2].*All elements have been processed, so calculate the sum of the elements…