# 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& nums) { constexpr int kMod = 1'000'000'007; const int kMax = *max_element(begin(nums), end(nums)); long ans = 0; // count[i] := # of nums <= i vector 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] := # 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