-
Notifications
You must be signed in to change notification settings - Fork 4.9k
/
SumOfFlooredPairs.cpp
68 lines (63 loc) · 1.97 KB
/
SumOfFlooredPairs.cpp
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Source : https://leetcode.com/problems/sum-of-floored-pairs/
// Author : Hao Chen
// Date : 2021-05-22
/*****************************************************************************************************
*
* 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 10^9 + 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 <= 10^5
* 1 <= nums[i] <= 10^5
******************************************************************************************************/
class Solution {
public:
int sumOfFlooredPairs(vector<int>& nums) {
const int MAX_NUM = 100001;
int cnt[MAX_NUM] = {0};
int maxn = 0;
for(auto& n : nums) {
cnt[n]++;
maxn = max(maxn, n);
}
vector<vector<int>> stats;
for(int i=1; i<MAX_NUM; i++) {
if (cnt[i] > 0) {
stats.push_back({i, cnt[i]});
}
cnt[i] += cnt[i-1];
}
const int MOD = 1e9+7;
int result = 0;
for(int i=0; i < stats.size(); i++) {
int n = stats[i][0];
int c = stats[i][1];
for(int x=2; x <= maxn/n+1; x++) {
int pre = (x-1) * n - 1;
int cur = min( x * n - 1, MAX_NUM-1);
result = (result + (cnt[cur] - cnt[pre]) * long(x-1) * c) % MOD;
}
}
return result;
}
};