Count Divisible Coin Selections
Reported by candidates from Google's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Google OA reported in December 2025 looks like a coin puzzle, but it reduces to counting subsets of a fixed size by sum remainder. That's a knapsack with a modulus. If you've got an invite in your inbox, the whole question is whether you spot the DP state fast. Coins are 0 to n-1, pick exactly k, sum divisible by m, answer mod 10^9 + 7. If you blank on the state design during the live assessment, StealthCoder sits invisibly on your screen as a safety net. Know the shape first, though.
The problem
There are n coins with values from 0 to n - 1, inclusive.
Return the number of ways to select exactly k coins such that the sum of the selected coin values is divisible by m.
Return the answer modulo 10^9 + 7.
Function
countDivisibleCoinSelections(n: int, m: int, k: int) → int
Examples
Example 1
n = 4
m = 2
k = 2
return = 2
The valid selections are {0,2} and {1,3}.
Example 2
n = 5
m = 3
k = 2
return = 3
Coin values are 0,1,2,3,4. The valid pairs are {0,3}, {1,2}, and {2,4}.
Constraints
1 <= n <= 200
1 <= m <= 100
0 <= k <= n
Coin values are exactly 0, 1,..., n - 1.
Return the answer modulo 10^9 + 7.Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick: you only care about each coin's value mod m, not the value itself. Use dp[j][r], the number of ways to pick j coins with sum remainder r. Loop over each coin value v from 0 to n-1, and update j downward from k to 1 so each coin is used once. Transition: dp[j][(r + v) % m] += dp[j-1][r]. The answer is dp[k][0]. Complexity is roughly n * k * m, which is 200 * 200 * 100 = 4 million operations, easily fine. Common pitfalls: iterating j upward, which reuses a coin, forgetting the modulo on every addition, and mishandling k = 0, where the answer is 1 because the empty sum 0 is divisible by m. Check example 1 by hand before submitting. StealthCoder is your hedge in the live OA if the rolling update order slips your mind.
StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.
You can drill Count Divisible Coin Selections cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. If you're reading this with an OA window open, you're who this was built for.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Google's OA.
Google reuses patterns across OAs. If you're reading this with an OA window open, you're who this was built for. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Count Divisible Coin Selections FAQ
What's the trick in Count Divisible Coin Selections?+
Track sums by remainder mod m instead of actual sums. Build dp[count][remainder] over the coins, adding each coin value mod m. The answer is dp[k][0]. The state space is tiny, so no clever math is needed.
How hard is this problem really?+
Medium. It's a standard 0/1 knapsack with one extra dimension for count. If you've done subset-sum or partition problems, this is the same skeleton. The constraints are small, so a plain triple loop passes.
Why must j iterate downward?+
Each coin can be picked once. Iterating j from k down to 1 means you read dp values from before the current coin was added. Going upward would let the same coin count multiple times and inflate the answer.
What edge cases should I test?+
Test k = 0, which should return 1. Test m = 1, where every sum is divisible, so the answer is C(n, k) mod 10^9 + 7. Test k = n, where there's exactly one selection. Also confirm both examples by hand.
How do I prepare for this in 48 hours?+
Write the 2D remainder knapsack from memory twice. Then solve one variant, like counting subsets with a target sum. Focus on loop order and modular addition. Skip fancy optimizations, since the limits don't require them.