Welcome to Subscribe On Youtube

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;
    }
}

  • // OJ: https://leetcode.com/problems/sum-of-floored-pairs/
// Time: O()
// Space: O()
class Solution {
public:
    int sumOfFlooredPairs(vector<int>& A) {
        unordered_map<int, int> freq;
        long prefix[100001] = {};
        long mx = *max_element(begin(A), end(A)), ans = 0, mod = 1e9 + 7;
        for (int n : A) freq[n]++;
        for (int i = 1; i <= mx; ++i) {
            prefix[i] += prefix[i - 1];
            if (freq.count(i)) prefix[i] += freq[i];
        }
        for (auto &[n, cnt] : freq) {
            for (long i = 1; i <= mx / n; ++i) {
                ans = (ans + i * cnt % mod * (prefix[min(n * (i + 1) - 1, mx)] - prefix[n * i - 1]) % mod) % mod;
            }
        }
        return ans;
    }
};

  • # 1862. Sum of Floored Pairs
# https://leetcode.com/problems/sum-of-floored-pairs

class Solution:
    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        M, N = 10 ** 9 + 7, 10 ** 5 + 1
        res = mmax = 0
        prefix = [0] * (2 * N + 1)
        
        for x in nums:
            mmax = max(mmax, x)
            prefix[x] += 1
        
        for i in range(1, len(prefix)):
            prefix[i] += prefix[i - 1]
        
        for num in nums:
            l, r, t = num, num * 2 - 1, 1
            
            while l <= mmax:
                res += (prefix[r] - prefix[l - 1]) * t
                l += num
                r += num
                t += 1
        
        return res % M


  • 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
}

  • 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;
}


  • 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
    }
}

All Problems

All Solutions