FastPrep
Problem

Count Divisible Coin Selections

Learn this problem
GoogleFULLTIMEOA
See Google hiring insights

Problem statement

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 = 4m = 2k = 2return = 2

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

Example 2

n = 5m = 3k = 2return = 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.

More Google problems

drafts saved locally
public int countDivisibleCoinSelections(int n, int m, int k) {
  // write your code here
}
n4
m2
k2
expected2
checking account