This question has been asked before, however none of them were answered definitively and I tried compiling all the information I found here. Feel free to merge/move to another stackexchange site if necessary.

Here are questions I found related to this:

• SPOJ:Card Shuffling
• Card Shuffling [SPOJ]

The problem was initially posted as an Interviewstreet Code Sprint, but right now it's listed as a practice problem. It's also been ported to SPOJ.

Here's the problem statement:

Here is an algorithm for shuffling N cards:

1) The cards are divided into K equal piles.

2) The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the initial pile is the bottom card of pile 1).

3) The next N / K cards from the bottom belong to pile 2, and so on.

4) Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2, ..., the Kth card of the shuffled pile is the top > card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.

For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".

Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?

Input: The first line contains the number of test cases T. The next T lines contain two integers each N and K.

Output: Output T lines, one for each test case containing the minimum number of shuffles needed. If the deck never comes back to its original order, output -1.

Constraints:

• K will be a factor of N.
• T <= 10000
• 2 <= K <= N <= 10^9

Spoiler Alert - don't read below if you want to solve it yourself.

The problem can be translated as:

Find the number of times a K-way (perfect) in-shuffle needs to be performed to restore a deck of N cards to its initial ordering.

I took two approaches to solving this problem. The first approach that came to mind was:

• find a formula that, given a position in the initial order would generate the card's next position
• use the formula to determine the number of shuffles it takes each card from the first pile (n / k in size) to return to its initial position
• return the least common multiple of the number of shuffles determined before

The complexity of this solution is O(n / k + max_number_of_suhffles). Here's the actual implementation. The problem with this is that it exceeds the maximum time, so I started to look for a formula that would allow me to get the number in near constant time.

The most I could optimize here (e.g. used some maps for caching computed values in the same permutation cycle etc.) was to make it pass 3/10 tests on interviewstreet.

I found this implementation, which assumes that the number of shuffles needed to return to the initial state is the multiplicative order of K relative to N + 1. From the wiki:

As a consequence of Lagrange's theorem, ordn(a) always divides φ(n). 

φ(n) is the Euler totient function, ordn is the group order - what we're looking for. I found this paper that uses φ to compute the number of shuffles, but it's only for a 2-way in-shuffle, not k-way.

Here are the steps for this implementation:

• precomputed the list of primes < 100 000
• computed φ(N+1) from its prime factors.
• determined all of φ(N + 1)'s factors by combining its prime factors in all possible ways.
• tried each factor in turn and get the smallest one, x, which verifies k ^ x % N + 1 = 1

This implementation is also posted on GitHub.

This runs really fast, but the automatic grader gives me a "wrong answer" classification for 9 out of 10 tests, both on SPOJ and Interviewstreet.

I tried comparing the output from the two implementations, but for the testcases I put in (known result and random), the two implementations always output the same thing. This is strange, since I'm pretty sure that the first algorithm is correct I assume that the second one should be as well.

The "wrong answer" classification could come from a runtime error in the code, but nothing jumps out as a possible cause for this.

I did not take into account the case in which no number shuffles can return the deck to the initial state - my understanding is that this is not possible. A finite number of perfect shuffles will eventually restore the initial ordering, even though the number of shuffles may be really high.

If you took the time to read this, thanks. :) I'm curious about the problem, I'd like to have it solved.