FastPrep
Problem · Math

Sum of Scores of Built Arrays

Learn this problem
● MediumUber logoUberOA
See Uber hiring insights

Problem statement

You have N ranges where the i-th range is from low[i] to high[i]. You need to create an array brr of length N. However, brr[i] can only be any prime number such that low[i] <= brr[i] <= high[i] for all possible i.

As we know there can be multiple ways to create brr. It is given that the score of an array is the multiplication of all values in it.

Your task is to find the sum of the score of all possible unique permutations of brr. Since the answer can be very large, return the answer modulo 10^9+7.

Note:

  • It is guaranteed that there will be at least one element in brr[i], which means there will always be a prime number between low[i] and high[i].
  • low[i] <= high[i] for all possible i (1 <= i <= N).

Function

sumOfScoresOfBuiltArrays(low: int[], high: int[]) → int

Examples

Example 1

low = [1, 3]high = [3, 5]return = 40

We have 2 ranges, [1,3] and [3,5], there can be 4 ways of choosing 'brr', [(2,3),(3,5), (2,5),(3,3)] and scores of these will be [6,15,10,9], so sum of scores will be 40.

Example 2

low = [1, 2, 2]high = [1, 2, 2]return = 8

There is only a single way to choose 'brr' as [2,2,2] hence the answer will be 8.

Example 3

low = [1, 2, 3]high = [4, 5, 30]return = 30

There is only a single way to choose 'brr' as [2,3,5] hence the answer will be 30.

Constraints

  • 1 <= N <= 10^5
  • 1 <= low[i], high[i] <= 10^6

More Uber problems

drafts saved locally
public int sumOfScoresOfBuiltArrays(int[] low, int[] high) {
  // write your code here
}
low[1, 3]
high[3, 5]
expected40
checking account