Free Hashing lessonsHashing · Stage 4 · Mastery · Step 3
Pairs that fill up a k
Count pairs whose sum is a multiple of k. About 12 minutes.
Shrink the numbers first
When only divisibility matters, a big number can be swapped for its remainder. Songs of 150 seconds and 30 seconds behave the same when you're checking for whole minutes: both leave 30 seconds over.
Once every value is small, the question often turns into one you've already solved. Ask what each item needs from its partner.
Try: ask what each item needs from its partner.
nums = [30, 20, 150, 100, 40], k = 60
30
020
130
240
340
4i
- seen
- {}
- pairs
- 0
Only remainders matter, so shrink every value: 150 → 30, 100 → 40, and so on.
Move 1 of 6
k = 60. A song lasts 150 seconds (remainder 30). Which partner remainders make a multiple of 60?
- A30
- B0
- C90
Show the answer
30. 30 + 30 = 60.
Pairs that fill up a k
Count the pairs of positions i < j where nums[i] + nums[j] is divisible by k.
nums = [30, 20, 150, 100, 40], k = 60 → 3
0 ≤ n ≤ 1,000,000 · 0 ≤ each value ≤ 10^9 · 1 ≤ k ≤ 100,000 · return a long
Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve