1862. Sum of Floored Pairs
Approach
Frequency prefix sums; for each value v iterate multiples k*v and add count[k*v] * k.
Key Techniques
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
// Approach: Frequency prefix sums; for each value v iterate multiples k*v and add count[k*v] * k.
// Time: O(max log max) Space: O(max)
public class Solution
{
public int SumOfFlooredPairs(int[] nums)
{
const int kMod = 1000000007;
int kMax = nums.Max();
long ans = 0;
// count[i] := the number of `nums` <= i
int[] count = new int[kMax + 1];
foreach (var num in 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)
{
int lo = i * j - 1;
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;
}
}