Scale Engineer

Sum of Floored Pairs

Hard
#1701Time: 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.
Patterns
MathPrefix Sum
Algorithms
Binary Search
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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).

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem