HardNo. 1862
Sum of Floored Pairs — LeetCode 1862 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Math, Binary Search, Prefix Sum
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- nums = [2,5,9]
- Output
- 10
- Explanation
- floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
Python solution
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 ansComplexity
- Time
- O(M × log M)
- Space · auxiliary
- O(M)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 1862. Sum of Floored Pairs is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0497 | Random Point in Non-overlapping Rectangles | Medium |
| 0528 | Random Pick with Weight | Medium |
| 0363 | Max Sum of Rectangle No Larger Than K | Hard |
| 0410 | Split Array Largest Sum | Hard |
| 0731 | My Calendar II | Medium |
| 0902 | Numbers At Most N Given Digit Set | Hard |
Frequently asked questions
- How hard is LeetCode 1862. Sum of Floored Pairs?
LeetCode 1862. Sum of Floored Pairs is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1862. Sum of Floored Pairs?
The Python solution on this page runs in O(M × log M).
- What is the space complexity of LeetCode 1862. Sum of Floored Pairs?
The Python solution on this page uses O(M) auxiliary space.
- What topics does LeetCode 1862. Sum of Floored Pairs cover?
LeetCode 1862. Sum of Floored Pairs is tagged Array, Math, Binary Search and Prefix Sum on LeetCode.