Floor Quotients of All Pairs

Hard

You get an array of positive integers values. For every ordered pair of indices (i, j), including pairs with i = j, take values[i] divided by values[j], rounded down to an integer. Return the sum of all these quotients modulo 10⁹ + 7.

Example 1

values=[3, 7, 4] → 7

The pairs with a non-zero quotient: 3/3, 7/7 and 4/4 give 1 each, 7/3 gives 2, 4/3 gives 1 and 7/4 gives 1. The sum is 3 + 2 + 1 + 1 = 7.

Example 2

values=[6, 6, 6] → 9

All nine ordered pairs give a quotient of 1.

Example 3

values=[1, 100000] → 100002

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Binary Search Prefix Sum

Similar problems

Pair GCDs by Sorted Position Hard Richest Plot Under the Cap Hard The Heaviest Reading Day Hard Best Average of a Long Stretch Hard Shortest Stretch Reaching a Total Hard

Input

values=[3, 7, 4]

Expected

Run checks the first 3 tests in your browser. Submit checks all 58 tests on the server, hidden ones included.