# 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

Question —

For any array of positive integers a[a..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             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] = . The maximum value in the array is 1. Add 1 to a = 1 so a’ = . 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 so a’ = [3, 2]. The largest value is 3. Add it to a = 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).

I write about Technical stuff, interview questions, and finance Deep Learning, LLM, Startup, Influencer, Executive, Data Science Manager