Description#
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 <= 1051 <= nums[i] <= 105
Solutions#
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$.
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$.
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int sumOfFlooredPairs(int[] nums) {
final int mod = (int) 1e9 + 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
const int mod = 1e9 + 7;
int mx = *max_element(nums.begin(), nums.end());
vector<int> cnt(mx + 1);
vector<int> s(mx + 1);
for (int x : nums) {
++cnt[x];
}
for (int i = 1; i <= mx; ++i) {
s[i] = s[i - 1] + cnt[i];
}
long long ans = 0;
for (int y = 1; y <= mx; ++y) {
if (cnt[y]) {
for (int d = 1; d * y <= mx; ++d) {
ans += 1LL * cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1]);
ans %= mod;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func sumOfFlooredPairs(nums []int) (ans int) {
mx := slices.Max(nums)
cnt := make([]int, mx+1)
s := make([]int, mx+1)
for _, x := range nums {
cnt[x]++
}
for i := 1; i <= mx; i++ {
s[i] = s[i-1] + cnt[i]
}
const mod int = 1e9 + 7
for y := 1; y <= mx; y++ {
if cnt[y] > 0 {
for d := 1; d*y <= mx; d++ {
ans += d * cnt[y] * (s[min((d+1)*y-1, mx)] - s[d*y-1])
ans %= mod
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| function sumOfFlooredPairs(nums: number[]): number {
const mx = Math.max(...nums);
const cnt: number[] = Array(mx + 1).fill(0);
const s: number[] = Array(mx + 1).fill(0);
for (const x of nums) {
++cnt[x];
}
for (let i = 1; i <= mx; ++i) {
s[i] = s[i - 1] + cnt[i];
}
let ans = 0;
const mod = 1e9 + 7;
for (let y = 1; y <= mx; ++y) {
if (cnt[y]) {
for (let d = 1; d * y <= mx; ++d) {
ans += cnt[y] * d * (s[Math.min((d + 1) * y - 1, mx)] - s[d * y - 1]);
ans %= mod;
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| impl Solution {
pub fn sum_of_floored_pairs(nums: Vec<i32>) -> i32 {
const MOD: i32 = 1_000_000_007;
let mut mx = 0;
for &x in nums.iter() {
mx = mx.max(x);
}
let mut cnt = vec![0; (mx + 1) as usize];
let mut s = vec![0; (mx + 1) as usize];
for &x in nums.iter() {
cnt[x as usize] += 1;
}
for i in 1..=mx as usize {
s[i] = s[i - 1] + cnt[i];
}
let mut ans = 0;
for y in 1..=mx as usize {
if cnt[y] > 0 {
let mut d = 1;
while d * y <= (mx as usize) {
ans +=
((cnt[y] as i64) *
(d as i64) *
(s[std::cmp::min(mx as usize, d * y + y - 1)] - s[d * y - 1])) %
(MOD as i64);
ans %= MOD as i64;
d += 1;
}
}
}
ans as i32
}
}
|
