1862. Sum of Floored Pairs LeetCode Solution

In this guide, you will get 1862. Sum of Floored Pairs LeetCode Solution with the best time and space complexity. The solution to Sum of Floored Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sum of Floored Pairs solution in C++
Sum of Floored Pairs solution in Java
Sum of Floored Pairs solution in Python
Additional Resources

1862. Sum of Floored Pairs LeetCode Solution image

Problem Statement of Sum of Floored Pairs

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

Complexity Analysis

Time Complexity: O(n + k\log k), where k = \max(\texttt{nums})
Space Complexity: O(n)

1862. Sum of Floored Pairs LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

1862. Sum of Floored Pairs LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

1862. Sum of Floored Pairs LeetCode Solution in Python

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
 # code by PROGIEZ