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^51 <= 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;
}
}