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.

#1862

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

向下取整数对和

给你一个整数数组 nums ，请你返回所有下标对 0 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大，请你返回答案对 10 9 + 7 取余的结果。函数 floor() 返回输入数字的整数部分。示例 1：输入： nums = [2,5,9] 输出： 10 …

数组数学二分查找前缀和

题目描述

给你一个整数数组 nums ，请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大，请你返回答案对10⁹ + 7 取余的结果。

函数 floor() 返回输入数字的整数部分。

示例 1：

输入：nums = [2,5,9]
输出：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
我们计算每一个数对商向下取整的结果并求和得到 10 。

示例 2：

输入：nums = [7,7,7,7,7,7,7]
输出：49

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：值域前缀和 + 优化枚举

我们先统计数组 $nums$ 中每个元素出现的次数，记录在数组 $cnt$ 中，然后计算数组 $cnt$ 的前缀和，记录在数组 $s$ 中，即 $s[i]$ 表示小于等于 $i$ 的元素的个数。

接下来，我们枚举分母 $y$ 以及商 $d$ ，利用前缀和数组计算得到分子的个数 $s[\min(mx, d \times y + y - 1)] - s[d \times y - 1]$ ，其中 $mx$ 表示数组 $nums$ 中的最大值。那么，我们将分子的个数，乘以分母的个数 $cnt[y]$ ，再乘以商 $d$ ，就可以得到所有满足条件的分式的值，将这些值累加起来，就可以得到答案。

时间复杂度 $O(M \times \log M)$ ，空间复杂度 $O(M)$ ，其中 $M$ 表示数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1872 石子游戏 VIII #1878 矩阵中最大的三个菱形和 #1838 最高频元素的频数