Algorithms – Solving the Algorithmic Problem of Picking Cards

algorithms

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:
6

Sample Input:
0 0 0 0 
Sample Output:
24

Sample Input:
0 0 1
Sample Output
4

Sample Input:
0 3 3
Sample Output:
0

Best Answer

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;
    }
    System.out.println(numberOfWays);
}

}

Related Topic