Skip to content

1862. Sum of Floored Pairs 👍

  • Time: $O(n + k\log k)$, where $k = \max(\texttt{nums})$
  • Space: $O(n)$
 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
class Solution {
 public:
  int sumOfFlooredPairs(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int kMax = ranges::max(nums);
    long ans = 0;
    // count[i] := the number of `nums` <= i
    vector<int> count(kMax + 1);

    for (const int num : nums)
      ++count[num];

    for (int i = 1; i <= kMax; ++i)
      count[i] += count[i - 1];

    for (int i = 1; i <= kMax; ++i)
      if (count[i] > count[i - 1]) {
        long sum = 0;
        for (int j = 1; i * j <= kMax; ++j) {
          const int lo = i * j - 1;
          const int hi = i * (j + 1) - 1;
          sum += (count[min(hi, kMax)] - count[lo]) * j;
        }
        ans += sum * (count[i] - count[i - 1]);
        ans %= kMod;
      }

    return ans;
  }
};

 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
class Solution {
  public int sumOfFlooredPairs(int[] nums) {
    final int kMod = 1_000_000_007;
    final int kMax = Arrays.stream(nums).max().getAsInt();
    long ans = 0;
    // count[i] := the number of `nums` <= i
    int[] count = new int[kMax + 1];

    for (final int num : nums)
      ++count[num];

    for (int i = 1; i <= kMax; ++i)
      count[i] += count[i - 1];

    for (int i = 1; i <= kMax; ++i)
      if (count[i] > count[i - 1]) {
        long sum = 0;
        for (int j = 1; i * j <= kMax; ++j) {
          final int lo = i * j - 1;
          final int hi = i * (j + 1) - 1;
          sum += (count[Math.min(hi, kMax)] - count[lo]) * (long) j;
        }
        ans += sum * (count[i] - count[i - 1]);
        ans %= kMod;
      }

    return (int) ans;
  }
}

 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
class Solution:
  def sumOfFlooredPairs(self, nums: list[int]) -> int:
    kMod = 1_000_000_007
    kMax = max(nums)
    ans = 0
    count = [0] * (kMax + 1)

    for num in nums:
      count[num] += 1

    for i in range(1, kMax + 1):
      count[i] += count[i - 1]

    for i in range(1, kMax + 1):
      if count[i] > count[i - 1]:
        summ = 0
        j = 1
        while i * j <= kMax:
          lo = i * j - 1
          hi = i * (j + 1) - 1
          summ += (count[min(hi, kMax)] - count[lo]) * j
          j += 1
        ans += summ * (count[i] - count[i - 1])
        ans %= kMod

    return ans