magic sequence of cards recursive algorithm

Question

I was asked this question in an interview and I couldnt answer completely. Infact the interviewer himself was confused. Was wondering if anyone knew the clear details of the question and the answer as well.

From what I remember, the question is something like this:

• If you had n cards, you get a magic sequence by first putting the 1st card face up on the table, inserting the 1+1 (i.e) 2 cards at the end of the deck, taking the next (3rd) card and putting it face up on the table, taking 3+1 i.e 4 cards and inserting them at the end of the deck.

  So basically, every iteration, you take one card put it face down on the table, and insert i+1 cards at the end of the deck.

This is what I understood from the question, I could have gotten a few details wrong. But in any case, the question now is:

• given a value n (so lets n=5 and so cards are say A,2,3,4,5)
• Find the kth value in the magic sequence formed by these cards.

Apparently this can be solved by recursion without having to do the operations till n. I suggested that I'd get the magic sequence first and then return the kth element but apparently there is a better way. Also, wanted to know if anyone knew the complete details of this question.

thanks!

Answer 1

I'm not sure exactly how to go about it, but I think one way might be to solve/simplify the recurrence relation:

f(1) = 1
f(2) = 3
f(3) = 7
f(4) = 15

f(k) = 2 * f(k-1) + 1 (mod n)

Or, as some like to call it,

2^k - 1 (mod n)

...shh