The problem below appeared on the last Code Sprint 2 programming competition (it's over already). The base cases are clear, but developing an algorithm that solves all possible cases has been a challenge so far.

There are N cards on the table and each has a number between 0 and N on it. Let us denote the number on the Nth Ni. You want to pick up all the cards, but you can only pick a specific Nth card if you already picked Ni cards before. (As an example, if a card has a value of 3 on it, you can’t pick that card up unless you’ve already picked up 3 cards previously) In how many ways can all the cards be picked up?

Input are the cards with their respective numbers, and the output should be the total number of ways possible to pick them up.

Sample Input:
0 0 0 
Sample Output:

Sample Input:
0 0 0 0 
Sample Output:

Sample Input:
0 0 1
Sample Output

Sample Input:
0 3 3
Sample Output:

3 Answers 3


Here's a quick implementation in java. The idea is to find how many cards can be picked each step by counting the number of cards with a number below this step and subtracting the number of cards already picked. Of course a lot of work is unnecessarily repeated, but this should give a good idea of how to approach this problem.

public class PickCards {
public static int countLessOrEqualThanMax(int[] cards, int max) {
    int count = 0;
    for (int number : cards) {
        if(number <= max) count++;
    return count;

public static void main(String[] args) {
    int[] cards = {0, 1, 2, 4, 3};
    int numberOfWays = 1;
    for(int i = 0; i < cards.length; i++) {
        int ways = Math.max(0, countLessOrEqualThanMax(cards, i) - i);
        numberOfWays *= ways;


  • This answer is correct: you can reduce the running time to linear by using counting sort on the cards, precomputing the answers of countLessOrEqualThanMax and then iterating over the cards in their sorted order. Jan 9, 2012 at 15:39

As a starting point, for the case where all cards are zero:

Output = N!

For example:

Sample Input: 0 0 0

Sample Output: 3 x 2 x 1 = 6.

Clearly, any card with a number higher than 0 will reduce the number of possible ways of picking up the cards.

Any card with "N" on it will make it impossible to pick up the cards.


Consider N=4 cards where:

A=0, B=0, C=1, D=2

C can't appear in column 1. D can't appear in column 1 or 2.

  1. A, B, C, D - Y
  2. A, B, D, C - Y
  3. A, C, B, D - Y
  4. A, C, D, B - Y
  5. A, D, B, C - N
  6. A, D, C, B - N

  7. B, A, C, D - Y

  8. B, A, D, C - Y
  9. B, C, A, D - Y
  10. B, C, D, A - Y
  11. B, D, A, C - N
  12. B, D, C, A - N

  13. C, A, B, D - N

  14. C, A, D, B - N
  15. C, B, A, D - N
  16. C, B, D, A - N
  17. C, D, A, B - N
  18. C, D, B, A - N

  19. D, A, B, C - N

  20. D, A, C, B - N
  21. D, B, A, C - N
  22. D, B, C, A - N
  23. D, C, A, B - N
  24. D, C, B, A - N
  • Yep that far I had arrived as well. The challenge is to create an algorithm that will solve all the possible cases. Jan 9, 2012 at 12:23
  • @daniels: I've expanded my answer.
    – Kramii
    Jan 9, 2012 at 12:46
  • Kramil, that helps, but having the algorithm itself would help even more. I am taking a look FranKL's algo now. Looks like he nailed it, do you agree? Jan 9, 2012 at 13:09
  • @daniels: FrankL's method looks fine, but is a lot of work when a simple formula can give the answer.
    – Kramii
    Jan 9, 2012 at 13:16
  • @Kramil, And what's that formula? Cause I agree a formula would be ideal, but I fail to see how we could develop one single formula that solves all possible inputs. Jan 9, 2012 at 13:36

The algorithm in pseudocode isn't efficient, but it will find ALL cases

   //Create an array that stores card number, 
   //position, and a flag that denotes it is picked or not, 
   //initialize with not picked:
   (1, 10 , false) , ( 2, 9, false) .....

   // try to pick each item in array, 
   // and spawn a new sub-process tree for each possible move
   // try all cards one by one
   for i = 1 until N 
       if ARRAY[i].ispicked 
           // just skip it if its already picked
           do nothing 
           // if its pickable hurray, but we are not 
           // generating a sub-process tree if it is not a valid case
           if ARRAY[i].number <= ARRAY[].Count(ispicked) 
               // pick it
               ARRAY[i].ispicked = true
               // spawn a new array tree for each possible 
               // move for the subtree generated
   if ARRAY[].Count(ispicked) = N
       // we have picked all cards, lets ad plus one to our total

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.