#1862

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Sum of Floored Pairs

The problem asks to calculate the sum of floor divisions for all pairs in a given integer array, using an efficient method to avoid brute force.

array math binary search prefix sum

Problem Statement

Given an integer array nums, your task is to return the sum of the floor division of each pair of elements nums[i] and nums[j], where 0 <= i, j < nums.length. The floor division is calculated as the integer part of the division of nums[i] by nums[j]. Since the result can be too large, return it modulo 10^9 + 7.

For example, given the array nums = [2, 5, 9], you need to compute the sum of floor(nums[i] / nums[j]) for every pair of indices i and j. A brute force solution would involve iterating through all pairs, which is inefficient for larger arrays, but using binary search and frequency counting can optimize the approach.

Examples

Example 1

Input: nums = [2,5,9]

Output: 10

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

Example details omitted.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 105

Solution Approach

Frequency Counting

The first step is to calculate the frequency of each number in the array. This helps in reducing redundant calculations when computing the sum of floor divisions for pairs. This frequency-based approach enables efficient accumulation of results.

Binary Search Over Answer Space

The key insight for optimization lies in performing binary search over the valid answer space. Instead of calculating the floor for every pair directly, use binary search to identify how many values contribute to a certain floor value, thus speeding up the process.

Prefix Sum

Prefix sums can be used to efficiently compute the sum of floor divisions in the context of the frequency counts. By leveraging prefix sums, we can quickly sum the values for all valid pairs, ensuring an efficient solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach. A naive solution could take O(n^2) time, which is too slow for large inputs. However, using frequency counting combined with binary search reduces the time complexity significantly, making the solution more scalable to the input size. The space complexity is dominated by the frequency array and prefix sums, both of which require O(n) space.

What Interviewers Usually Probe

The candidate demonstrates an understanding of binary search and its application to optimize the problem.
The candidate efficiently utilizes frequency counting and prefix sums to reduce redundant calculations.
The candidate is able to explain the trade-offs between brute force and optimized solutions clearly.

Common Pitfalls or Variants

Common pitfalls

Failing to use binary search efficiently over the answer space, leading to unnecessary iterations.
Not considering the modulo operation, which could result in integer overflow for large inputs.
Misunderstanding how to calculate the frequency of elements, leading to incorrect accumulation of results.

Follow-up variants

What if the array contains only one element? How would the solution change?
How would the solution change if we were to compute the sum of floor divisions for only unique pairs?
What if we were asked to compute the sum of divisions (instead of floor) for all pairs?

FAQ

How do I optimize the brute force solution for this problem?

Optimizing the brute force solution involves using binary search over the answer space combined with frequency counting and prefix sums.

What is the time complexity of the optimized solution?

The optimized solution reduces the time complexity from O(n^2) to a more efficient approach using binary search and frequency counting.

What if the array is very large? How does the solution scale?

The optimized approach scales well to large arrays by reducing the need for pairwise floor division calculations, leveraging frequency counting and binary search.

What does 'floor division' mean in this context?

Floor division refers to the operation of dividing two integers and returning the largest integer less than or equal to the result.

How does GhostInterview help with this problem?

GhostInterview helps by breaking down the problem into manageable techniques and guiding you through efficient approaches like binary search and frequency counting.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#1872 stone game viii #1878 get biggest three rhombus sums in a grid #1838 frequency of the most frequent element