Question

1862. Sum of Floored Pairs

中文文档

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 <= 105
• 1 <= 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$.

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

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

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

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