Solution

Method 1 – Prefix Sum and Counting (Optimal)

Intuition

The key idea is to count, for each possible divisor, how many numbers in the array are divisible by it, and use prefix sums to efficiently compute the sum of floored pairs. Instead of brute-forcing all pairs, we use counting and prefix sums to reduce the time complexity.

Approach

Find the maximum value in the array (max_num).
Count the frequency of each number in nums.
Build a prefix sum array of frequencies.
For each possible divisor d from 1 to max_num, for each multiple of d, count how many numbers fall into that range and add count * freq[d] * k to the answer, where k is the floored value.
Return the answer modulo 10^9 + 7.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& nums) {\n        in

Related Tags