Sum of Floored Pairs - Video Solutions

Problem Overview: Given an integer array nums, compute the total value of floor(nums[i] / nums[j]) for every pair (i, j). A direct pairwise computation quickly becomes too slow because the array can contain up to 10⁵ values.

Approach 1: Naive Approach Using Nested Loop (Time: O(n²), Space: O(1))

The most direct method checks every ordered pair in the array. Use two nested loops and compute floor(nums[i] / nums[j]) for each pair. Accumulate the result while applying the required modulo. This approach is easy to implement and useful for validating logic on small inputs. However, with n up to 100k, the n² comparisons quickly become infeasible. The method does not use any special data structures and simply iterates through the array twice.

Approach 2: Optimized Counting and Prefix Sum (Time: ~O(M log M), Space: O(M))

The key observation: instead of iterating over pairs, group numbers by value and count how many fall into ranges that produce the same quotient. Build a frequency array for every value in nums. Then compute a prefix sum array so you can quickly query how many numbers lie inside a value range. For a fixed value x, all numbers in the interval [k*x, (k+1)*x - 1] produce floor(num / x) = k. Iterate over multiples of x, use the prefix sum to count elements in each interval, and accumulate k * count * freq[x]. This avoids explicit pair iteration and converts the problem into range counting. The technique relies heavily on math observations and fast range queries using prefix sums.

Recommended for interviews: Interviewers expect the counting + prefix sum solution. The brute force approach demonstrates that you understand the definition of the operation, but the optimized solution shows the real insight: convert pair comparisons into frequency-based range counting. Recognizing quotient ranges and iterating through multiples is the core trick that reduces the runtime enough to pass constraints.