Problem Description

You are given an integer array nums. You need to calculate the sum of floor(nums[i] / nums[j]) for all possible pairs of indices where 0 <= i, j < nums.length.

The floor() function returns the integer part of a division operation (rounds down to the nearest integer). For example, floor(7/3) = 2 and floor(5/2) = 2.

You need to:

1. Consider all possible pairs (i, j) from the array, including pairs where i = j
2. For each pair, calculate floor(nums[i] / nums[j])
3. Sum all these values together
4. Return the final sum modulo 10^9 + 7 (since the answer could be very large)

For example, if nums = [2, 5, 9], you would calculate:

• floor(2/2) + floor(2/5) + floor(2/9) = 1 + 0 + 0
• floor(5/2) + floor(5/5) + floor(5/9) = 2 + 1 + 0
• floor(9/2) + floor(9/5) + floor(9/9) = 4 + 1 + 1
• Total sum = 1 + 0 + 0 + 2 + 1 + 0 + 4 + 1 + 1 = 10

The challenge is to efficiently compute this sum, especially when the array is large, as a brute force approach checking all pairs would be too slow.

Intuition

Instead of computing floor(nums[i] / nums[j]) for every pair directly, let's think about this problem from a different angle. For a fixed denominator y and a fixed quotient d, we want to count how many numerators x satisfy floor(x / y) = d.

The key insight is that floor(x / y) = d when d * y <= x < (d + 1) * y. This means for a given denominator y and quotient d, the numerators that produce this quotient fall within the range [d * y, (d + 1) * y - 1].

Since we're dealing with counting elements in specific ranges, we can use a frequency count approach. First, count how many times each value appears in the array. Then, to efficiently query "how many elements fall in range [L, R]", we can use prefix sums on the frequency array.

The algorithm becomes:

1. Count the frequency of each element in nums
2. Build a prefix sum array where s[i] represents the count of elements with value <= i
3. For each possible denominator value y that appears in the array:
   • For each possible quotient d = 1, 2, 3, ...:
     • Calculate the range of numerators: [d * y, min(max_value, (d + 1) * y - 1)]
     • Use the prefix sum to find how many numerators fall in this range
     • Add cnt[y] * d * (count of numerators in range) to the answer
     • Stop when d * y > max_value since no numerators can be that large

This approach transforms the problem from O(n²) pair enumeration to O(max_value * log(max_value)) by cleverly grouping calculations by quotient values.

Learn more about Math, Binary Search and Prefix Sum patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Count Frequencies

cnt = Counter(nums)
mx = max(nums)

We use a Counter to count the frequency of each element in nums. We also find the maximum value mx in the array, which helps us determine the bounds for our calculations.

Step 2: Build Prefix Sum Array

s = [0] * (mx + 1)
for i in range(1, mx + 1):
    s[i] = s[i - 1] + cnt[i]

We create a prefix sum array s where s[i] represents the total count of elements with values <= i. This allows us to query the count of elements in any range [L, R] in O(1) time using s[R] - s[L-1].

Step 3: Enumerate Denominators and Quotients

ans = 0
for y in range(1, mx + 1):
    if cnt[y]:  # Only process if y exists in the array
        d = 1
        while d * y <= mx:
            # Calculate contribution
            d += 1

For each possible denominator value y from 1 to mx, we check if it actually exists in our array (cnt[y] > 0). If it does, we enumerate all possible quotients d.

Step 4: Calculate Contribution for Each (denominator, quotient) Pair

ans += cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1])
ans %= mod

For a fixed denominator y and quotient d, the numerators that produce floor(x/y) = d are in the range [d * y, (d + 1) * y - 1].

• The lower bound is d * y
• The upper bound is (d + 1) * y - 1, but we cap it at mx since no element exceeds mx
• Using the prefix sum array: s[min(mx, d * y + y - 1)] - s[d * y - 1] gives us the count of numerators in this range
• We multiply by cnt[y] (frequency of denominator) and d (the quotient value) to get the total contribution
• We take modulo at each step to prevent overflow

The algorithm continues until d * y > mx because beyond this point, there are no numerators large enough to produce a non-zero quotient.

Time Complexity: O(n + mx * log(mx)) where n is the length of the array and mx is the maximum value. The log factor comes from the fact that for each denominator y, we iterate through approximately mx/y quotients, and the sum mx/1 + mx/2 + ... + mx/mx is O(mx * log(mx)).

Space Complexity: O(mx) for storing the frequency count and prefix sum arrays.

Example Walkthrough

Let's walk through a small example with nums = [4, 3, 4, 5].

Step 1: Count Frequencies

• cnt = {3: 1, 4: 2, 5: 1}
• mx = 5 (maximum value)

Step 2: Build Prefix Sum Array

s[0] = 0
s[1] = 0 (no elements ≤ 1)
s[2] = 0 (no elements ≤ 2)
s[3] = 1 (one element ≤ 3, which is 3)
s[4] = 3 (three elements ≤ 4: one 3 and two 4s)
s[5] = 4 (all four elements ≤ 5)

Step 3: Process Each Denominator

For y = 3 (appears 1 time):

• d = 1: Range [3, 5], count = s[5] - s[2] = 4 - 0 = 4
  • Contribution: 1 × 1 × 4 = 4
  • (This means floor(3/3)=1, floor(4/3)=1, floor(4/3)=1, floor(5/3)=1)
• d = 2: Range [6, 8], but 6 > mx=5, so stop

For y = 4 (appears 2 times):

• d = 1: Range [4, 7], capped at [4, 5], count = s[5] - s[3] = 4 - 1 = 3
  • Contribution: 2 × 1 × 3 = 6
  • (Elements 4, 4, 5 give quotient 1 when divided by 4)
• d = 2: Range [8, 11], but 8 > mx=5, so stop

For y = 5 (appears 1 time):

• d = 1: Range [5, 9], capped at [5, 5], count = s[5] - s[4] = 4 - 3 = 1
  • Contribution: 1 × 1 × 1 = 1
  • (Only element 5 gives quotient 1 when divided by 5)
• d = 2: Range [10, 14], but 10 > mx=5, so stop

Total Sum = 4 + 6 + 1 = 11

Let's verify with brute force:

• floor(4/3)=1, floor(4/4)=1, floor(4/4)=1, floor(4/5)=0
• floor(3/3)=1, floor(3/4)=0, floor(3/4)=0, floor(3/5)=0
• floor(4/3)=1, floor(4/4)=1, floor(4/4)=1, floor(4/5)=0
• floor(5/3)=1, floor(5/4)=1, floor(5/4)=1, floor(5/5)=1

Sum = (1+1+1+0) + (1+0+0+0) + (1+1+1+0) + (1+1+1+1) = 3 + 1 + 3 + 4 = 11 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(M × log M)

The algorithm consists of three main parts:

1. Creating a Counter and finding the maximum value: O(n) where n is the length of nums
2. Building the prefix sum array: O(M) where M is the maximum value in nums
3. The nested loop calculation:
   • The outer loop iterates through values from 1 to M: O(M)
   • For each value y with cnt[y] > 0, the inner while loop runs while d * y <= M
   • This means d can go up to M/y, so the inner loop runs approximately M/y times
   • Summing across all y values: Σ(M/y) for y from 1 to M equals M × (1/1 + 1/2 + 1/3 + ... + 1/M)
   • This harmonic series sum is approximately O(log M)
   • Therefore, the total is O(M × log M)

Space Complexity: O(M)

The space usage comes from:

• Counter dictionary cnt: stores at most n unique values, but in worst case bounded by O(M)
• Prefix sum array s: has exactly M + 1 elements, so O(M)
• Other variables use constant space

The dominant space usage is O(M) from the prefix sum array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow Without Proper Modulo Operations

Pitfall: One of the most common mistakes is forgetting to apply the modulo operation frequently enough, leading to integer overflow even in languages like Python that handle big integers.

# WRONG: Accumulating large values without modulo
result += frequency[y] * multiplier * count_in_range
# If this gets too large before applying modulo at the end, 
# it can cause memory issues or slow performance

# CORRECT: Apply modulo after each addition
result += frequency[y] * multiplier * count_in_range
result %= MOD

2. Off-by-One Errors in Range Calculation

Pitfall: Incorrectly calculating the range of numerators that produce a specific quotient.

# WRONG: Forgetting the -1 in the upper bound
range_end = min(max_value, multiplier * y + y)  # This includes one extra element

# CORRECT: The range for quotient d is [d*y, (d+1)*y - 1]
range_end = min(max_value, multiplier * y + y - 1)

3. Incorrect Prefix Sum Query

Pitfall: Using wrong indices when querying the prefix sum array for range counts.

# WRONG: Off-by-one in the lower bound
count_in_range = prefix_sum[range_end] - prefix_sum[range_start]

# CORRECT: Subtract prefix_sum[range_start - 1] to include range_start
count_in_range = prefix_sum[range_end] - prefix_sum[range_start - 1]

4. Not Handling Edge Cases Properly

Pitfall: Failing to handle when range_start - 1 becomes negative (when multiplier = 1 and y = 1).

# SAFE APPROACH: Ensure we don't access negative indices
if range_start > 1:
    count_in_range = prefix_sum[range_end] - prefix_sum[range_start - 1]
else:
    count_in_range = prefix_sum[range_end]

5. Inefficient Loop Termination

Pitfall: Using an inefficient condition for the while loop that might cause unnecessary iterations.

# INEFFICIENT: Checking a condition that's always false after a point
while multiplier <= max_value:  # This could run max_value times even when unnecessary

# CORRECT: Stop when the lower bound of the range exceeds max_value
while multiplier * y <= max_value:  # More efficient termination

6. Memory Issues with Large Maximum Values

Pitfall: Creating arrays based on max(nums) without considering memory constraints.

# POTENTIAL ISSUE: If max(nums) is very large (e.g., 10^5)
prefix_sum = [0] * (max_value + 1)  # Could use significant memory

# SOLUTION: Consider using a dictionary-based approach if values are sparse
# or compress the value space if there are gaps

7. Forgetting to Check Element Existence

Pitfall: Processing all values from 1 to max_value without checking if they actually exist in the array.

# WRONG: Processing non-existent denominators
for y in range(1, max_value + 1):
    # Process y even if it's not in nums
  
# CORRECT: Skip if frequency is 0
for y in range(1, max_value + 1):
    if frequency[y] == 0:
        continue

Best Practice Solution: Always validate your range calculations with small examples, apply modulo operations consistently, and carefully handle array boundary conditions to avoid these common pitfalls.