Solution


Approach 1: Brute Force

Intuition

We can try every possible X.

Algorithm

Since we divide the deck of N cards into say, K piles of X cards each, we must have N % X == 0.

Then, say the deck has C_i copies of cards with number i. Each group with number i has X copies, so we must have C_i % X == 0. These are necessary and sufficient conditions.

Complexity Analysis

  • Time Complexity: , where is the number of cards. It is outside the scope of this article to prove that the number of divisors of is bounded by .

  • Space Complexity: .


Approach 2: Greatest Common Divisor

Intuition and Algorithm

Again, say there are C_i cards of number i. These must be broken down into piles of X cards each, ie. C_i % X == 0 for all i.

Thus, X must divide the greatest common divisor of C_i. If this greatest common divisor g is greater than 1, then X = g will satisfy. Otherwise, it won't.

Complexity Analysis

  • Time Complexity: , where is the number of votes. If there are cards with number , then each gcd operation is naively . Better bounds exist, but are outside the scope of this article to develop.

  • Space Complexity: .


Analysis written by: @awice.