# Sum of Floored Pairs
**Difficulty:** HARD
[External](https://leetcode.com/problems/sum-of-floored-pairs)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-floored-pairs
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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** `109 + 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 <= 105`
* `1 <= nums[i] <= 105`

# Approaches
## 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.
**Time:** 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:** O(1), as we only use a few variables to store the sum and loop counters.
**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.
### Explanation
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`.

```java
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);
    }
}
```
### 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)`.

## Frequency Count Optimization
The brute-force approach performs many redundant calculations if the input array contains duplicate numbers. For example, if `nums = [2, 2, 5]`, the calculation for `floor(5/2)` is done twice. We can optimize this by first counting the occurrences of each unique number.
**Time:** O(N + M^2), where N is `nums.length` and M is `max(nums)`. Populating the frequency array takes O(N). The nested loops run up to M*M times. With M up to 10^5, M^2 is 10^10, which is still too slow. · **Space:** O(M) to store the frequency counts, where M is the maximum value in `nums`.
**Pros:** More efficient than pure brute-force if N is much larger than M (the maximum value).
**Cons:** The O(M^2) complexity makes it too slow for the given constraints on the values in `nums`.
### Explanation
We can express the total sum as `Σ (count(x) * count(y) * floor(x / y))` for all unique pairs of numbers `(x, y)` present in the array.
1. First, find the maximum value `maxVal` in `nums`.
2. Create a frequency array `counts` of size `maxVal + 1` and populate it by iterating through `nums`.
3. Then, use two nested loops to iterate through all possible pairs of values `(x, y)` from `1` to `maxVal`.
4. If both `x` and `y` are present in the original array (i.e., `counts[x] > 0` and `counts[y] > 0`), we calculate their contribution to the total sum, which is `counts[x] * counts[y] * (x / y)`.
5. We add this contribution to a running total, taking the modulo at each step.

```java
class Solution {
    public int sumOfFlooredPairs(int[] nums) {
        int MOD = 1_000_000_007;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        int[] counts = new int[maxVal + 1];
        for (int num : nums) {
            counts[num]++;
        }

        long totalSum = 0;
        for (int x = 1; x <= maxVal; x++) {
            if (counts[x] == 0) continue;
            for (int y = 1; y <= maxVal; y++) {
                if (counts[y] == 0) continue;
                long quotient = x / y;
                long contribution = (long)counts[x] * counts[y] * quotient;
                totalSum = (totalSum + contribution) % MOD;
            }
        }
        return (int)totalSum;
    }
}
```
### Algorithm
- Find the maximum value `maxVal` in `nums`.
- Create a frequency array `counts` of size `maxVal + 1` and populate it.
- Initialize `totalSum = 0L` and `MOD = 10^9 + 7`.
- Iterate `x` from `1` to `maxVal`.
    - If `counts[x] == 0`, continue.
    - Iterate `y` from `1` to `maxVal`.
        - If `counts[y] == 0`, continue.
        - Calculate `quotient = x / y`.
        - Calculate `contribution = (long)counts[x] * counts[y] * quotient`.
        - Update `totalSum = (totalSum + contribution) % MOD`.
- Return `(int)totalSum`.

## Frequency Count with Prefix Sums
This approach improves upon the previous methods by first counting the frequency of each number and then changing the perspective of the summation. Instead of iterating through all pairs `(nums[i], nums[j])`, we iterate through each possible divisor `y` and for each `y`, we efficiently calculate the sum of `floor(x / y)` over all numbers `x` present in the input array. This efficient calculation is achieved by grouping numbers `x` that yield the same quotient `k = floor(x / y)` and using a prefix sum array on the frequencies to quickly find the count of numbers in any range.
**Time:** O(N + M * log(M)), where N is the length of `nums` and M is the maximum value in `nums`. Populating `counts` and `prefixCounts` takes O(N + M). The nested loops' complexity is Σ_{y=1 to M} (M/y), which is the Harmonic series, approximately M * log(M). · **Space:** O(M) for the `counts` and `prefixCounts` arrays, where M is the maximum value in `nums`.
**Pros:** Efficient enough to pass the given constraints.; Correctly handles all cases by leveraging number theory concepts (sum over multiples).
**Cons:** Requires O(M) extra space, which could be large if the maximum value is large.; The logic is more involved than simpler approaches.
### Explanation
1. First, we determine the maximum value (`maxVal`) in the `nums` array.
2. We create a frequency array, `counts`, of size `maxVal + 1` to store the count of each number in `nums`.
3. We then create a prefix sum array, `prefixCounts`, also of size `maxVal + 1`. `prefixCounts[i]` will store the total count of numbers in `nums` that are less than or equal to `i`. This allows us to find the count of numbers in any range `[a, b]` in `O(1)` time using `prefixCounts[b] - prefixCounts[a-1]`.
4. The main logic iterates through each possible divisor `y` from `1` to `maxVal`. We only proceed if `y` is actually present in the input array (i.e., `counts[y] > 0`).
5. For each such divisor `y`, we calculate `sum_for_y = Σ_x counts[x] * floor(x/y)`. To do this efficiently, we iterate through multiples of `y`. For each multiple `m = k * y`, all numbers `x` in the range `[m, m + y - 1]` have `floor(x/y) = k`.
6. We use the `prefixCounts` array to find how many numbers from the original `nums` array fall into this range. Let this be `count_in_range`.
7. The contribution to `sum_for_y` from this range is `k * count_in_range`. We sum these contributions for all `k`.
8. The total contribution to the final answer for the divisor `y` is `counts[y] * sum_for_y`.
9. We sum up these contributions for all `y` to get the final result, taking the modulo at each step to prevent overflow.

```java
class Solution {
    public int sumOfFlooredPairs(int[] nums) {
        int MOD = 1_000_000_007;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        int[] counts = new int[maxVal + 1];
        for (int num : nums) {
            counts[num]++;
        }

        long[] prefixCounts = new long[maxVal + 1];
        for (int i = 1; i <= maxVal; i++) {
            prefixCounts[i] = prefixCounts[i - 1] + counts[i];
        }

        long totalSum = 0;
        for (int y = 1; y <= maxVal; y++) {
            if (counts[y] == 0) {
                continue;
            }
            long sumForY = 0;
            for (long m = y; m <= maxVal; m += y) {
                long k = m / y;
                int upper = (int)Math.min(m + y - 1, maxVal);
                long countInRange = prefixCounts[upper] - prefixCounts[(int)m - 1];
                sumForY = (sumForY + k * countInRange) % MOD;
            }
            totalSum = (totalSum + (long)counts[y] * sumForY) % MOD;
        }

        return (int)totalSum;
    }
}
```
### Algorithm
- Find the maximum value `maxVal` in `nums`.
- Create a frequency array `counts` of size `maxVal + 1` and populate it by iterating through `nums`.
- Create a prefix sum array `prefixCounts` of size `maxVal + 1` from the `counts` array.
- Initialize `totalSum = 0` and `MOD = 10^9 + 7`.
- Loop for `y` from `1` to `maxVal`:
    - If `counts[y] == 0`, continue.
    - Initialize `sumForY = 0`.
    - Loop for `m` from `y` to `maxVal` with a step of `y` (i.e., `m = y, 2y, 3y, ...`):
        - Calculate quotient `k = m / y`.
        - Define the upper bound of the range: `upper = m + y - 1`.
        - Find the count of numbers in `nums` within the range `[m, upper]`: `countInRange = prefixCounts[min(upper, maxVal)] - prefixCounts[m - 1]`.
        - Add the contribution to `sumForY`: `sumForY = (sumForY + (long)k * countInRange) % MOD`.
    - Add the total contribution for divisor `y` to `totalSum`: `totalSum = (totalSum + (long)counts[y] * sumForY) % MOD`.
- Return `totalSum`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumOfFlooredPairs(vector<int> &nums) {
    const int mod = 1e9 + 7;
    int mx = *max_element(nums.begin(), nums.end());
    vector<int> cnt(mx + 1);
    vector<int> s(mx + 1);
    for (int x : nums) {
      ++cnt[x];
    }
    for (int i = 1; i <= mx; ++i) {
      s[i] = s[i - 1] + cnt[i];
    }
    long long ans = 0;
    for (int y = 1; y <= mx; ++y) {
      if (cnt[y]) {
        for (int d = 1; d * y <= mx; ++d) {
          ans += 1LL * cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1]);
          ans %= mod;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int: mod = 10 ** 9 + 7 cnt = Counter(nums) mx = max(nums) s = [0] * (mx + 1) for i in range(1, mx + 1): s[i] = s[i - 1] + cnt[i] ans = 0 for y in range(1, mx + 1): if cnt[y]: d = 1 while d * y <= mx: ans += cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1]) ans %= mod d += 1 return ans

```