LeetCode 1862 - Sum of Floored Pairs

The problem asks us to calculate the sum of the integer division results, floor(nums[i] / nums[j]), for every pair of elements (i, j) in a given array nums. Here, floor() represents the largest integer less than or equal to the division result.

leetcodehardarraymathbinary-searchcountingenumerationprefix-sum

LeetCode Problem 1862

Difficulty: 🔴 Hard
Topics: Array, Math, Binary Search, Counting, Enumeration, Prefix Sum

Solution

Problem Understanding

The problem asks us to calculate the sum of the integer division results, floor(nums[i] / nums[j]), for every pair of elements (i, j) in a given array nums. Here, floor() represents the largest integer less than or equal to the division result. The array nums can have up to 10^5 elements, and each element can also be as large as 10^5. Since the total number of pairs is n^2, a naive computation could lead to 10^10 operations, which is infeasible.

The input nums is simply a list of positive integers. The expected output is the sum of all floored divisions for every pair, modulo 10^9 + 7. This modulo ensures that extremely large sums can be handled without integer overflow.

Important edge cases include arrays where all numbers are the same, arrays with only one element, and arrays with elements of varying magnitudes that could produce divisions resulting in zero. The constraints guarantee that the input is non-empty and contains only positive integers, which simplifies handling divisions by zero.

Approaches

The brute-force approach is straightforward: iterate through every pair (i, j), compute floor(nums[i] / nums[j]), and sum the results. This is correct because it directly follows the problem definition, but it is far too slow for the input limits, since it requires O(n^2) operations.

The optimal approach leverages the observation that if we know how many elements fall into certain ranges, we can compute contributions of nums[i] to the sum in batches rather than individually. Specifically, for a fixed nums[j] = x, the value floor(nums[i] / x) only changes at multiples of x. If we precompute the frequency of each number, we can efficiently sum contributions for ranges of nums[i] rather than for each individual element.

We can also use prefix sums or a count array to quickly calculate how many numbers fall within a given range of multiples, which reduces the time complexity dramatically.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Directly iterate over all pairs
Optimal O(n * maxNum) O(maxNum) Use counting and prefix sums to batch contributions

Algorithm Walkthrough

  1. Identify the maximum number maxNum in nums to define the range for counting frequencies.
  2. Create a frequency array count of size maxNum + 1, where count[x] stores how many times x appears in nums.
  3. Build a prefix sum array prefix from the frequency array, where prefix[i] represents the number of elements in nums less than or equal to i.
  4. Initialize result = 0 to accumulate the sum.
  5. For each x in nums, compute the contribution of x for all multiples of x up to maxNum. For a given multiple k*x, the number of elements nums[i] in the range [k*x, (k+1)*x - 1] contributes k to the sum. Use the prefix array to quickly count how many elements fall in that range.
  6. Add the computed contribution to result, taking modulo 10^9 + 7.
  7. Return result.

Why it works: By iterating over multiples of each number and using prefix sums to count elements efficiently, the algorithm ensures that every pair (i, j) is accounted for without redundant computation. The contribution of each number is correctly weighted by the integer division result.

Python Solution

from typing import List

class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        max_num = max(nums)
        count = [0] * (max_num + 1)
        
        for num in nums:
            count[num] += 1
        
        prefix = [0] * (max_num + 2)
        for i in range(1, max_num + 1):
            prefix[i] = prefix[i - 1] + count[i]
        
        result = 0
        for x in nums:
            k = 1
            while k * x <= max_num:
                left = k * x
                right = min(max_num, (k + 1) * x - 1)
                contribution = k * (prefix[right] - prefix[left - 1])
                result = (result + contribution) % MOD
                k += 1
        
        return result

The Python implementation first calculates the frequency of each number and then builds the prefix sum. For each element, it sums contributions over ranges defined by multiples of the element. Modulo is applied at each step to prevent overflow.

Go Solution

func sumOfFlooredPairs(nums []int) int {
    const MOD = 1_000_000_007
    maxNum := 0
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }

    count := make([]int, maxNum+1)
    for _, num := range nums {
        count[num]++
    }

    prefix := make([]int, maxNum+2)
    for i := 1; i <= maxNum; i++ {
        prefix[i] = prefix[i-1] + count[i]
    }

    result := 0
    for _, x := range nums {
        k := 1
        for k*x <= maxNum {
            left := k * x
            right := (k+1)*x - 1
            if right > maxNum {
                right = maxNum
            }
            contribution := k * (prefix[right] - prefix[left-1])
            result = (result + contribution) % MOD
            k++
        }
    }

    return result
}

The Go implementation mirrors the Python approach. Arrays are initialized for counting and prefix sums. Care is taken to ensure array bounds are correct, and integer overflow is avoided using modulo.

Worked Examples

Example 1: nums = [2,5,9]

  1. maxNum = 9
  2. count = [0,0,1,0,0,1,0,0,0,1]
  3. prefix = [0,0,1,1,1,2,2,2,2,3,3]
  4. For x = 2:
  • k = 1: range [2,3] → contribution = 1*(prefix[3]-prefix[1]) = 1*(1-0)=1
  • k = 2: range [4,5] → contribution = 2*(prefix[5]-prefix[3]) = 2*(2-1)=2
  • k = 3: range [6,7] → contribution = 3*(prefix[7]-prefix[5]) = 3*(2-2)=0
  • k = 4: range [8,9] → contribution = 4*(prefix[9]-prefix[7]) = 4*(3-2)=4
  1. Repeat for x = 5 and x = 9, summing contributions = 10

Example 2: nums = [7,7,7,7,7,7,7]

  • Each element contributes 7 pairs with floor division 1. Total sum = 7*7 = 49

Complexity Analysis

Measure Complexity Explanation
Time O(n + n * sqrt(maxNum))) Counting and prefix sum O(n + maxNum), contributions are bounded by multiples ≤ maxNum
Space O(maxNum) Arrays for counting and prefix sums

The time complexity is much lower than brute-force because we aggregate contributions via multiples rather than iterating over all pairs.

Test Cases

# provided examples
assert Solution().sumOfFlooredPairs([2,5,9]) == 10  # Example 1
assert Solution().sumOfFlooredPairs([7,7,7,7,7,7,7]) == 49  # Example 2

# edge cases
assert Solution().sumOfFlooredPairs([1]) == 1  # single element
assert Solution().sumOfFlooredPairs([1,2,3]) == 5  # small varied elements
assert Solution().sumOfFlooredPairs([100000]*5) == 25  # max element repeated
assert Solution().sumOfFlooredPairs([1,100000]) == 2  # extreme difference
Test Why
[2,5,9] Standard case with mixed numbers
[7,7,7,7,7,7,7] All elements equal
[1] Single element array
[1,2,3] Small varied numbers to check floor calculation
[100000]*5 Large repeated numbers to check efficiency
[1,100000] Extreme difference to test contribution counting

Edge Cases

Single Element Array: The only element divides itself, yielding 1. This ensures the code correctly handles the lower bound.

All Elements Equal: Every division yields 1, which is simple but tests summing of repeated values.

Maximum Value Elements: When elements are at 10^5, the code must handle large numbers without exceeding array bounds or integer limits. Prefix sums and modulo prevent overflow