Card Shuffling (SPOJ / Interviewstreet)

Question

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.

Answer 1

This is what I came up with after some observations I've done on paper.

class CardShuffle {
    private long k;
    private long n;
    private long kn;
    private long kn2;

    public CardShuffle(long k, long n) {
            //I omitted some checks done here
        this.k = k;
        this.n = n;
        this.kn = k / n;
        this.kn2 = k - kn;
    }

    public long shuffle() {
        long count = 0L;
        long next = 0L;
        do {
               //this can be further optimized
           next = kn2 - kn * (next % n) + (next / n); 
           ++count;
        } while((next != 0L) && (count < k));
        if(count > k)
           return -1;
        return count;
    }
}

The results are...

Testing 1000000 : 2
#ms: 3.121905
#ms: 1424.487191
#1: 9900 #2: 9900
Testing 1000000 : 5
#ms: 1.409955
#ms: 556.329366
#1: 2475 #2: 2475
Testing 1000000 : 10
#ms: 0.007823
#ms: 186.797204
#1: 12 #2: 12
Testing 1000000 : 20
#ms: 0.590298
#ms: 275.751527
#1: 4950 #2: 4950
Testing 1000000 : 25
#ms: 0.298642
#ms: 260.559372
#1: 2475 #2: 2475
Testing 1000000 : 40
#ms: 1.187581
#ms: 241.956729
#1: 9900 #2: 9900
Testing 1000000 : 50
#ms: 1.187581
#ms: 241.015548
#1: 9900 #2: 9900
Testing 9999999 : 41841
#ms: 14.499887
#ms: 1829.868042
#1: 125000 #2: 125000
Testing 9999999 : 3333333
#ms: 58.119398
#ms: 311.005728
#1: 500000 #2: 500000
Testing 9999999 : 13947
#ms: 52.704185
#ms: 2095.336418
#1: 500000 #2: 500000

tested against this input...

10
1000000 2
1000000 5
1000000 10
1000000 20
1000000 25
1000000 40
1000000 50
9999999 41841
9999999 3333333
9999999 13947

First #ms is time in milliseconds it took my method, second is yours. #1 and #2 are the results respectively.

Where-as for this input...

15
1000000000 2
1000000000 5
1000000000 10
1000000000 20
1000000000 25
1000000000 40
1000000000 50
1000000000 1000
1000000000 200000000
1000000000 250000000
1000000000 500000000
1000000000 50000000
999999999 1001001
999999999 37037037
999999999 333333333

My method finds the solution in

Testing 1000000000 : 2
#ms: 71.360466
#1: 525780
Testing 1000000000 : 5
#ms: 68.987259
#1: 525780
Testing 1000000000 : 10
#ms: 0.008381
#1: 18
Testing 1000000000 : 20
#ms: 75.608492
#1: 525780
Testing 1000000000 : 25
#ms: 31.843154
#1: 262890
Testing 1000000000 : 40
#ms: 33.014531
#1: 262890
Testing 1000000000 : 50
#ms: 84.27384
#1: 525780
Testing 1000000000 : 1000
#ms: 0.006705
#1: 6
Testing 1000000000 : 200000000
#ms: 53.991778
#1: 525780
Testing 1000000000 : 250000000
#ms: 43.765898
#1: 262890
Testing 1000000000 : 500000000
#ms: 54.457201
#1: 525780
Testing 1000000000 : 50000000
#ms: 68.080999
#1: 525780
Testing 999999999 : 1001001
#ms: 115.060154
#1: 1000000
Testing 999999999 : 37037037
#ms: 5783.539528
#1: 50000000
Testing 999999999 : 333333333
#ms: 5391.880532
#1: 50000000

while yours goes out of memory on the very first one, on my old and slow laptop though.

I haven't validated this approach yet, but looks to me like it works. You might try and see if it fails on some inputs. I'd appreciate it.

If you're interested a bit more how I developed the formula, leave a comment.

I too have submitted the solution to interviewstreet but it failed on the 4th testcase due to the time limit constraint.

I'll try with a c program very soon and will report here.