Leetcode Problem 1862. Sum of Floored Pairs

1862. Sum of Floored Pairs

Leetcode Solutions

Prefix Sum and Counting Sort Approach

  1. Find the maximum value in nums and create a frequency array freq of size max_val + 1 to store the count of each number in nums.
  2. Compute the prefix sums of the frequency array to get the cumulative frequency prefix_sum.
  3. Initialize total_sum to 0 to store the final result.
  4. Iterate over each unique number num in nums.
  5. For each num, iterate over its multiples m up to max_val.
  6. For each multiple m, calculate the range [m * num, (m + 1) * num - 1] and use prefix_sum to find the count of elements in this range.
  7. Multiply the count by m and add it to total_sum, applying the modulo operation.
  8. Multiply total_sum by the frequency of num and add it to the final result, again applying the modulo operation.
  9. Return the final result modulo 10^9 + 7.
UML Thumbnail

Brute Force with Optimization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...