Sum of Floored Pairs

HARD

Description

Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the array. Since the answer may be too large, return it modulo 10⁹ + 7.

The floor() function returns the integer part of the division.

Example 1:

Input: nums = [2,5,9]
Output: 10
Explanation:
floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
floor(5 / 2) = 2
floor(9 / 2) = 4
floor(9 / 5) = 1
We calculate the floor of the division for every pair of indices in the array then sum them up.

Example 2:

Input: nums = [7,7,7,7,7,7,7]
Output: 49

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Sum of Floored Pairs. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

The most straightforward solution is to simulate the process directly. We can use nested loops to iterate through every possible pair of indices (i, j) in the nums array. For each pair, we calculate floor(nums[i] / nums[j]) and add it to a running total.

Algorithm

Initialize totalSum = 0L and MOD = 10^9 + 7.
Iterate i from 0 to nums.length - 1.
Iterate j from 0 to nums.length - 1.

  Calculate `quotient = nums[i] / nums[j]`.

```
  Add `quotient` to `totalSum`.
```
Return (int)(totalSum % MOD).

We initialize a variable sum to zero. We then set up two nested loops, both iterating from 0 to nums.length - 1. The outer loop variable can be i and the inner loop variable j. Inside the inner loop, we compute the integer division nums[i] / nums[j] and add the result to sum. To handle the large potential sum, we should use a long for the sum variable. The final result is this sum modulo 10^9 + 7.

class Solution {
    public int sumOfFlooredPairs(int[] nums) {
        long totalSum = 0;
        int MOD = 1_000_000_007;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] != 0) { // Although constraints say nums[i] >= 1, good practice.
                    totalSum += nums[i] / nums[j];
                }
            }
        }
        return (int)(totalSum % MOD);
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of `nums`. With N up to 10^5, this is approximately 10^10 operations, which is too slow.Space Complexity: O(1), as we only use a few variables to store the sum and loop counters.

Pros and Cons

Pros:

Very simple to understand and implement.
Requires no extra space.

Cons:

Highly inefficient for the given constraints and will result in a Time Limit Exceeded (TLE) error.

Code Solutions

Checking out 3 solutions in different languages for Sum of Floored Pairs. Click on different languages to view the code.

class Solution {
public
  int sumOfFlooredPairs(int[] nums) {
    final int mod = (int)1 e9 + 7;
    int mx = 0;
    for (int x : nums) {
      mx = Math.max(mx, x);
    }
    int[] cnt = new int[mx + 1];
    int[] s = new int[mx + 1];
    for (int x : nums) {
      ++cnt[x];
    }
    for (int i = 1; i <= mx; ++i) {
      s[i] = s[i - 1] + cnt[i];
    }
    long ans = 0;
    for (int y = 1; y <= mx; ++y) {
      if (cnt[y] > 0) {
        for (int d = 1; d * y <= mx; ++d) {
          ans +=
              1L * cnt[y] * d * (s[Math.min(mx, d * y + y - 1)] - s[d * y - 1]);
          ans %= mod;
        }
      }
    }
    return (int)ans;
  }
}

Video Solution

Watch the video walkthrough for Sum of Floored Pairs

Algorithms:

Binary Search

Patterns:

MathPrefix Sum

Data Structures:

Array