CareerCup

Interesting question, I think it can be done in O(n) worst case time complexity using symmetric groups (if I understand the question correctly).

First of all, here is the way I understood the question:
1. There is a Deck (Queue of cards) and a Table (Stack of cards). The Deck contains n distinct cards.
2. In each iteration step (that is - an inner step in one iteration) - two cards are removed from the Deck (removed from the Deck). The first is place at the Table (pushed to the Stack) and the second is added to the back of the Deck (added to the Queue).
3. Step 2 is repeated until the Deck contains 1 card which is then removed from the Deck and placed on the Table (pushed to the Stack).
4. We collect the cards on the table and build a new Deck according to their current order (pop cards from the Stack and push them into the Queue). Steps 1-4 are considered a single iteration.
5. Repeat steps (1)-(4) until we restore the original Deck order.

Example for n=4:
Initial Deck = {0,1,2,3}
After 1 iteration: {3,1,2,0}
After 2 iterations: {0,1,2,3}

Which means that 2 iterations are required to restore the initial state.



My approach would be to determine how the cards are permuted in each iteration and use this information to find out how many iterations would be needed to restore the original state.

The first iteration implies the permutation on the deck elements (the permutation is applied on the indices, not on the elements themselves) and the same permutation applies for every subsequent iteration (the deck elements order may be different but as mentioned the permutation applies only to the indices of the elements, not the elements themselves). This implies that finding the number of iterations is equivalent to finding the order of the initial permutation (in the symmetric group Sn).
The order of a permutation can be found by calculating the lcm (least common multiply) of all the cycle lengths in the cycle representation of the permutation. We'll also use the fact that lcm(a,b) = (a*b) / gcd(a,b) and Euclid's algorithm for calculating the gcd.

Here are two examples for this approach:
Example 1 (n=4): Initial deck is {0,1,2,3}. The deck after 1 iteration is {3,1,2,0} The corresponding permutation p is defined as follows: p(0)=3, p(1)=1, p(2)=2, p(3)=0 (it receives the index of an element in the deck at the beginning of the iteration and returns the index of the same element at the end of the iteration). The cycle representation of p is: p= (0 3) (think of p as an array which represents several circular linked lists and find all these lists/cycles within the array - cycles whose length is 1 are considered trivial). This means that p contains a single non trivial cycle whose length is 2 and thus the order of p is 2. In other words p^2 = identity permutation. Applying this to our example:
Iteration 1: p({0,1,2,3}) = {3,1,2,0}
Iteration 2: p({3,1,2,0}) = p(p({0,1,2,3})) = p^2({0,1,2,3}) = identity({0,1,2,3}) = {0,1,2,3}

Thus the number of iterations required for this case is 2.

Example 2 (n=3): Initial deck is {0,1,2}. The deck after 1 iteration is {1,2,0}. The permutation p is defined as follows: p(0)=2,p(1)=0,p(2)=1. The cycle representation of p is p = (0 2 1). The permutation p has a single non trivial cycle whose length is 3, this means that p's order is 3, in other words p^3 = identity. Applying this to our example:
Iteration 1: p({0,1,2}) = {1,2,0}
Iteration 2: p({1,2,0}) = p(p({0,1,2})) = p^2({0,1,2})={2,0,1}
Iteration 3: p({2,0,1}) = p(p({1,2,0})) = p(p(p({0,1,2}))) = p^3({0,1,2}) = identity({0,1,2}) = {0,1,2}

Thus the number of iterations is 3.

Implementation:
1. Find the permutation p by performing a single iteration - can be done in O(n) using a Queue and a Stack.

2. Find all the non-trivial cycle lengths of the permutation p. We can view the permutation p as an array where p[i] is the new index of the the element in index i. Finding the lengths of all the cycles in the array p can be done in a similar fashion to finding the number of elements in a circular list (two pointers, one slow and the other is fast and the length will be determined when they meet). We can maintain a flag array to mark all the indices we've already visited so that we won't check the same cycle twice. Overall complexity of this step: O(n).

3. Once we have all the cycle lengths, we need to calculate the lcm of them. This is done by using the identity lcm(a,b) = (a*b) / gcd(a,b). The time complexity for finding the gcd(a,b) is O(logm) where m = min(a,b) (I may be wrong here, please correct me if I am). Suppose there are k non-trivial cycles and their lengths are m1,m2,...,mk. First we calculate lcm(1,m1) - O(log(m1)). Then lcm(lcm(1,m1),m2) - O(log(m2)). And so on, the overall run-time will be:

O(log(m1)) + O(log(m2)) + ... + O(log(mk)) <= O(m1) + O(m2) + ... + O(mk) <= O(n)

Because the total sum of the cycle lengths is less/equal than the number of elements - n.

4. Return the lcm which was calculated in the previous step.


Code:
Permutation class:

public static class Permutation {
		private final int[] permutation;
		
		private void validateLegalPermutation(int[] permutation){
			if (permutation==null){
				throw new NullPointerException("permutation is null");
			}
			int res = 0;
			for (int i=0;i<permutation.length;i++){
				res ^= permutation[i]^(i);
			}
			
			if (res!=0){
				throw new IllegalArgumentException("illegal permutation, may include duplicate elements");
			}
		}
		
		public Permutation(int[] permutation){
			validateLegalPermutation(permutation);
			this.permutation = permutation;
		}
		
		private static int gcd(int a, int b){
			if ((a<=1) || (b<=1)){return 1;}
			
			int max = Math.max(a, b);
			int min = Math.min(a, b);
			while ((min>1) && (max>min)){
				max = max - min;
				int tmp = Math.max(max, min);
				min = Math.min(max, min);
				max = tmp;
			}
			
			return min;
		}
		
		private static int lcm(int a, int b){
			return ((a*b)/gcd(a,b));
		}
		
		private int findCycleLength(int index, boolean[] seen){
			if ((index<0) || (index>=permutation.length)){
				throw new ArrayIndexOutOfBoundsException("illegal starting index");
			}
			if ((seen==null) || (seen.length!=permutation.length)){
				throw new IllegalArgumentException("seen array either null or not in the right size");
			}
			
			int slow = index;
			int fast = index;
			int length = 0;
			do {
				seen[slow]=true;
				slow = permutation[slow];
				fast = permutation[permutation[fast]];
				length++;
			} while (slow!=fast);
			
			return length;
		}

Helper Methods:

private Stack<Integer> getCycleLengths(){
			boolean[] seen = new boolean[permutation.length];
			for (int i=0;i<seen.length;i++){seen[i]=false;}
			
			Stack<Integer> cycles = new Stack<Integer>();
			for (int i=0;i<permutation.length;i++){
				if (!seen[i]){
					int cLength = findCycleLength(i,seen);
					if (cLength>1){
						cycles.push(cLength);
					}
				}
			}
			
			return cycles;
		}
		
		private int getCyclesLCM(Stack<Integer> cycles){
			if (cycles==null){return 1;}
			
			int lcm = 1;
			while (!cycles.isEmpty()){
				int cur = cycles.pop();
				lcm = Permutation.lcm(lcm, cur);
			}
			
			return lcm;
		}
		
		public int getOrder(){
			return getCyclesLCM(getCycleLengths());
		}
	}
	
	private static int[] performIteration(Queue<Integer> deck){
		if ((deck==null) || (deck.isEmpty())){return null;}
		
		Stack<Integer> table = new Stack<Integer>();
		while (!deck.isEmpty()){
			table.push(deck.poll());
			if (!deck.isEmpty()){deck.offer(deck.poll());}
		}
		int[] p = new int[table.size()];
		for (int i=0;i<p.length;i++){p[i] = table.pop();}
		
		return p;
	}

The main method to calculate the number of iterations:

public static int getNumberOfIterations(int n){
		if (n<=1){return 0;}
		
		Queue<Integer> deck = new LinkedList<Integer>();
		for (int i=0;i<n;i++){deck.offer(i);}
		Permutation initialPerm = new Permutation(performIteration(deck));
		
		return initialPerm.getOrder();
	}

Total 52 cards would be there, So It would take 51 Iterations.
( If number of cards are odd then number of iterations would be same as number of cards.)
(If number of cards are even then number of iterations = number of cards - 1.

Kartik,
YFor 1,2,3,4 the order will be like below:

Table	Deck
------------
1 2 3 4
1 3          4 2
1 3 4       2
1 3 4 2

1  4            2 3
1 4 2 	  3
1 4 2 3

1 2       3 4
1 2 3 4

Here is the brute method:

int PopACard(vector<int>& cards){
	if (cards.empty()) return -1;
	int card = cards[0];
	cards.erase(cards.begin());
	if (!cards.empty()){
		int top = cards[0];
		cards.erase(cards.begin());
		cards.push_back(top);
	}
	return card;
}
int iter(vector<int>& cards){
	vector<int> cur = cards;
	vector<int> next;
	int step = 0;
	bool same = false;
	while (!same){
		step++;
		while (!cur.empty()){
			next.push_back(PopACard(cur));
		}
		swap(cur, next);
		reverse(cur.begin(), cur.end());
		if (cards==cur)
			same = true;
	}
	return step;
}

1. Suppose the cards are saved in an array In;
2. Build a stack Out;
3. Partition In into two parts:
Left part: all the cards with odd index;
Right part: the rest cards;
push the left part into stack Out;
4. recursively call the partition function on the Right part till no card's in Right part;
5. Out.pop();
6. Above is one iteration: O(n3/2+n3/4+n3/8+...)~O(3n)

Do the iteration repeatedly till Out.pop() is your original deck.

import java.util.*;
public class CardDeckProb {

	public static void main(String[] args) {
			int deck[]={1,2,3,4,5,6,7,8};
			Queue<Integer> queue=new java.util.LinkedList<Integer>();
			addCardsToQueue(deck,queue);
			
			boolean cardOnTable=true;
			int deckSize=deck.length;
			int suffledDeck[]=new int[deckSize];
			int card=0;
			int arrayPostion=0;
			int iteratonCount=0;
			
		while (!Arrays.equals(deck, suffledDeck)) {
			cardOnTable = true;
			arrayPostion=deckSize-1;
			while (queue.size() > 0) {
				card = queue.element();
				if (cardOnTable || queue.size() == 1) {
					suffledDeck[arrayPostion] = card;
					cardOnTable = false;
					arrayPostion--;
				} else {
					queue.offer(card);
					cardOnTable = true;
				}
				queue.poll();

			}
			addCardsToQueue(suffledDeck, queue);
			iteratonCount++;
		}
		
		System.out.println("Iteration Count : "+iteratonCount);
	}

	private static void addCardsToQueue(int[] deck, Queue<Integer> queue) {
		for(int card : deck)
		{
			queue.offer(card);
		}
	}
}

The answer is 510 iterations for a deck of 52 cards. Here is the C++ program to compute this:

#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

void deck_of_cards_main(){
  queue<int> deck;
  stack<int> table;
  int n = 52;
  for(int i=1;i<=n;++i){
      deck.push(i);
  }


  int i=0;
  while(i<5000){
      bool flag=false;
      while(!deck.empty()){
          if(!flag){
              int tmp = deck.front();
              deck.pop();
              table.push(tmp);
              flag=true;
          }else{
              int tmp = deck.front();
              deck.pop();
              deck.push(tmp);
              flag=false;
          }
      }

      vector<int> deck_vec;
      std::cout<<++i<<". ";
      while(!table.empty()){
          int tmp = table.top();
          std::cout<<tmp<<",";
          deck.push(tmp);
          deck_vec.push_back(tmp);
          table.pop();
      }
      std::cout<<"\n";

      vector<int>::const_iterator itr = adjacent_find(deck_vec.begin(),deck_vec.end(),greater<int>());

      if(itr==deck_vec.end())
        break;
  }
  std::cout<<"\n"<<"Number of iterations="<<i<<"\n";
}

Hello I would like to you ask suggestion for this problem without java.util* by using system.arraycopy