Problem 272. Generalized N-Cards Problem

Preface: This is a generalized version of the problem I presented here.

You have a deck of N cards numbered in order from 1 to N. You are given a pattern to discard a certain number of cards and move a number of cards to the bottom of the deck. Eventually, you will have one card left. What is the number of that card?

The sequence of discarding/moving cards will be given in a row vector of 1s and -1s where 1 represents moving a card to the bottom of the deck and -1 represents discarding a card. This sequence should be repeated until there is only one card left (e.g. [-1 1] would return this problem to the non-generalized case).

Example

    generalNCardsProblem(5,[-1 1])
    deck = [ 1 2 3 4 5 ]
    deck = [ 2 3 4 5 ]
    deck = [ 3 4 5 2 ]
    deck = [ 4 5 2 ]
    deck = [ 5 2 4 ]
    deck = [ 2 4 ]
    deck = [ 4 2 ]
    deck = [ 2 ]

    generalNCardsProblem(5,[-1 1 1 -1])
    deck = [ 1 2 3 4 5 ]
    deck = [ 2 3 4 5 ]
    deck = [ 3 4 5 2 ]
    deck = [ 4 5 2 3 ]
    deck = [ 5 2 3 ]
    deck = [ 2 3 ]
    deck = [ 3 2 ]
    deck = [ 2 3 ]
    deck = [ 3 ]