Skip to main content
Talentd

Sum of Floored Pairs - Solution & Explanation

HardArrayMathBinary SearchPrefix Sum19 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given an integer array nums, compute the total value of floor(nums[i] / nums[j]) for every pair (i, j). A direct pairwise computation quickly becomes too slow because the array can contain up to 105 values.

Approach 1: Naive Approach Using Nested Loop (Time: O(nĀ²), Space: O(1))

The most direct method checks every ordered pair in the array. Use two nested loops and compute floor(nums[i] / nums[j]) for each pair. Accumulate the result while applying the required modulo. This approach is easy to implement and useful for validating logic on small inputs. However, with n up to 100k, the nĀ² comparisons quickly become infeasible. The method does not use any special data structures and simply iterates through the array twice.

Approach 2: Optimized Counting and Prefix Sum (Time: ~O(M log M), Space: O(M))

The key observation: instead of iterating over pairs, group numbers by value and count how many fall into ranges that produce the same quotient. Build a frequency array for every value in nums. Then compute a prefix sum array so you can quickly query how many numbers lie inside a value range. For a fixed value x, all numbers in the interval [k*x, (k+1)*x - 1] produce floor(num / x) = k. Iterate over multiples of x, use the prefix sum to count elements in each interval, and accumulate k * count * freq[x]. This avoids explicit pair iteration and converts the problem into range counting. The technique relies heavily on math observations and fast range queries using prefix sums.

Recommended for interviews: Interviewers expect the counting + prefix sum solution. The brute force approach demonstrates that you understand the definition of the operation, but the optimized solution shows the real insight: convert pair comparisons into frequency-based range counting. Recognizing quotient ranges and iterating through multiples is the core trick that reduces the runtime enough to pass constraints.

Approach 1: Naive Approach Using Nested Loop

This is the straightforward approach where you loop through all pairs of elements in the array and compute the floor division of each pair. While not efficient for large arrays, it helps understand the problem better.

This C solution employs two nested loops to iterate over each pair in the array and calculates the floor division using the integer division operator. It sums up these floor divisions modulo 10^9 + 7.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) - iterating over each pair of elements.
Space Complexity: O(1) - no additional space required.

Try this approach in the editor ā†’

Approach 2: Optimized Approach Using Counting and Prefix Sum

This approach involves pre-computation using a counting array to determine the frequency of each element, then using this data to quickly compute sum of floored pairs using properties of division.

The C solution leverages a count array to store the frequency of each number up to the given maximum value (100,000) and prefix sum to allow efficient computation of range sums.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + max * log(max)) - counting and prefix processing.
Space Complexity: O(max) - space used for count and prefix arrays.

Try this approach in the editor ā†’

Approach 3: Prefix Sum of Value Range + Optimized Enumeration

First, we count the occurrences of each element in the array nums and record them in the array cnt. Then, we calculate the prefix sum of the array cnt and record it in the array s, i.e., s[i] represents the count of elements less than or equal to i.

Next, we enumerate the denominator y and the quotient d. Using the prefix sum array, we can calculate the count of the numerator s[min(mx, d times y + y - 1)] - s[d times y - 1], where mx represents the maximum value in the array nums. Then, we multiply the count of the numerator by the count of the denominator cnt[y], and then multiply by the quotient d. This gives us the value of all fractions that meet the conditions. By summing these values, we can get the answer.

The time complexity is O(M times log M), and the space complexity is O(M). Here, M is the maximum value in the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Naive Approach Using Nested Loop

Time Complexity: O(n^2) - iterating over each pair of elements.
Space Complexity: O(1) - no additional space required.

Optimized Approach Using Counting and Prefix Sum

Time Complexity: O(n + max * log(max)) - counting and prefix processing.
Space Complexity: O(max) - space used for count and prefix arrays.

Prefix Sum of Value Range + Optimized Enumerationā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Nested LoopO(nĀ²)O(1)Small input sizes or verifying correctness during development
Counting + Prefix Sum Optimization~O(M log M)O(M)Large arrays where value range is bounded; required for passing competitive programming constraints

Video Solution

Sum of Floored Pairs | Prefix Sum | Sieve Technique | Leetcode Hard | 1862 LeetCode ā€¢ CodeWithSunny ā€¢ 2,100 views views

Watch 4 more video solutions ā†’

Frequently Asked Questions

Is Sum of Floored Pairs easy or hard?
Sum of Floored Pairs is classified as a hard problem. The difficulty comes from recognizing that direct pair iteration is too slow and discovering the mathematical observation that floor division results form predictable value ranges. Efficient solutions rely on counting and prefix sum techniques.
Sum of Floored Pairs Python/Java solution
Most implementations follow the same structure across languages: build a frequency array, compute prefix sums, iterate through multiples of each value, and accumulate contributions modulo 1e9+7. This approach works efficiently in Python, Java, C++, and other languages because the heavy work is done with array indexing.
How to solve Sum of Floored Pairs in O(n)?
A strict O(n) solution is not typical because the algorithm depends on the maximum value range. The closest practical optimization uses a frequency array and prefix sums, then iterates through multiples of each number. This reduces the work to about O(M log M), which performs efficiently for constraints where M ā‰¤ 100000.
What is the best approach for Sum of Floored Pairs?
The best approach uses frequency counting combined with a prefix sum array. Instead of evaluating every pair, group numbers by value and count how many fall in ranges that produce the same floor division result. Iterating through multiples of each value allows computing contributions efficiently in about O(M log M) time.
Is Sum of Floored Pairs asked at Google/Amazon/Meta?
Hard array and math problems involving counting tricks and prefix sums frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the technique of grouping values and computing contributions through ranges is a common interview pattern.
What data structure is used in Sum of Floored Pairs?
The optimized solution uses arrays for frequency counting and a prefix sum array for fast range queries. These structures allow constant-time retrieval of how many numbers fall within a numeric interval, which is essential for computing floor division contributions efficiently.
What is the time complexity of Sum of Floored Pairs?
The brute force method runs in O(n^2) time because it evaluates every pair. The optimized approach uses counting and prefix sums with range queries, reducing the complexity to roughly O(M log M), where M is the maximum value in the array. Space complexity is O(M) for the frequency and prefix arrays.

Ready to solve this problem?

Practice Sum of Floored Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays