FastPrep
Problem

Count Divisible Coin Selections

FULLTIMEOA
See Google online assessment and hiring insights

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.

Examples
01 · Example 1
n = 4
m = 2
k = 2
return = 2

The valid selections are {0,2} and {1,3}.

02 · 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, m, k <= 10^3
  • Coin values are exactly 0, 1, ..., n - 1.
More Google problems
drafts saved locally
public int countDivisibleCoinSelections(int n, int m, int k) {
  // write your code here
}
n4
m2
k2
expected2
sign in to submit