FastPrepCount Divisible Coin Selections
Problems/Count Divisible Coin Selections

Count Divisible Coin Selections

Google logoGoogleFULLTIMEOA

Updated Jul 2026

QuestionFunctionExamplesConstraints

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 Online Assessment questions

  • Book Reading EveningsOA · Seen Nov 2026
  • Count Score CategoriesOA · Seen Nov 2026
  • Minimum Cars for Rental RequestsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Shortest Path in a Binary MatrixOA · Seen Nov 2026
  • Robot Assembly Line ConflictsOA · Seen Oct 2026
  • Assign LockerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Biggest Number From DigitsOA · Seen Oct 2026
  • Consolidate On-Call RotationsOA · PHONE SCREEN · Seen Oct 2026
  • Decreasing SubsequencesOA · Seen Sep 2026
  • Minimize Absolute Difference of Server LoadsOA · Seen Sep 2026

Interview reports that mention this question

  • Google OA: What It Tests (2026)

Google interview experiences

  • Google L5 Security Engineer Domain Knowledge Round: 1 Experience
  • Google Software Engineer Onsite Questions: 10 Experiences
  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int countDivisibleCoinSelections(int n, int m, int k) {
      // write your code here
    }
}
Checking account…