Formatted question description: https://leetcode.ca/all/1862.html
1862. Sum of Floored Pairs
Level
Hard
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 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
Solution
Sort the array nums
. Loop over nums
, use a hash map to store each number’s last index in nums
and use a tree map to store each number’s occurrences. Then loop over nums
again. For each num
in nums
, loop over all elements that are greater or equal to num
and find the number of times each quotient is counted. Use the hash map to obtain the count of num
and use the tree map to obtain the number of times each quotient is counted, and update the sum. Finally, return the sum.
class Solution {
public int sumOfFlooredPairs(int[] nums) {
final int MODULO = 1000000007;
Arrays.sort(nums);
Map<Integer, Integer> startIndices = new HashMap<Integer, Integer>();
Map<Integer, Integer> endIndices = new HashMap<Integer, Integer>();
TreeMap<Integer, Integer> counts = new TreeMap<Integer, Integer>();
int length = nums.length;
for (int i = 0; i < length; i++) {
int num = nums[i];
if (!startIndices.containsKey(num))
startIndices.put(num, i);
endIndices.put(num, i);
counts.put(num, counts.getOrDefault(num, 0) + 1);
}
long sum = 0;
for (int i = 0; i < length; i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
int num = nums[i];
int count = counts.get(num);
int j = i;
while (j < length) {
int quotient = nums[j] / num;
int next = num * (quotient + 1);
Integer maxNum = counts.floorKey(next - 1);
int endIndex = endIndices.get(maxNum);
int range = endIndex - j + 1;
sum = (sum + (long) count * (long) quotient * (long) range) % MODULO;
j = endIndex + 1;
}
}
return (int) sum;
}
}