# HackerRank Coding Interview 6. Prefix Scores

--

**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:*2*.*score(a)*when*k = 1*is*2.**2 modulo*(10*⁹ +7) = 2.* - In the second iteration,
*k = 2.*The array to consider is*a = arr[1:2] = [1, 2]*. The maximum value is*2*. Add*2*to*a[1] = 1*so*a’ = [3, 2].*The largest value is*3*. Add it to*a[2] = 2*so*a’ = [3, 5].**score(a)*when*k = 2*is*8.**8 modulo*(10*⁹ +7) = 8.* - Repeat the process for
*k = 3*.

Return *[2, 8, 19],* an array of scores for each value of *k.* Since the sums may become large, each value should be calculated modulo (*10⁹ +7).*

**Function Description**

Complete the function *getPrefixScores* in the editor below.

*getPrefixScores *has the following parameter:

*int arr[n]:* an array of integers

**Returns**

*int[[n]:* the scores for each value of *k, *modulo *(10⁹ + 7)*.