CareerCup

I would suggest using a circular linked list and working backwards.
So you start with a K, you would place cards from the bottom to the top (reversed from the way you will select them).

First you have K. You rotate it 13 times, but you can just rotate 13 mod 1 = 0.
Next you put Q on top. You rotate is 12 times, but you can just rotate 12 mod 2 = 0.
Next you put J on top. You rotate 11 times, but you can just rotate 11 mod 3 = 2 times.

Eventually you have the full set.

Untested sample code:

var top = new Node {Value = 13};
            top.Next = top;
            var count = 1;

            for (var i = 12; i > 0; i--)
            {
                count++;
                var node = new Node {Value = i, Next = top.Next };
                top.Next = node;
                top = node;

                var rotate = i%count;
                for (var x = 0; x < rotate; x++)
                {
                    top = top.Next;
                }
            }

Not sure how to prove that as nlogn time, but it seems efficient.

heap data structure will be the data structure i would choose. maintain highest card on top, and each time you pop the root node, the biggest one will become to top one. NLogN to create the heap structure.

can't we use doubly linked list.Once i reached the last node .I'll try to see if it is the min element
and if it is .
8<->9<->7<->K<->6<->3<->4<->1
Go back to 4 and delete the element. and print it
8<->9<->7<->K<->6<->4 . now since 4 is not the min element . First Go back and now my pointer will point to 3. and Remove the element and add to the head of the list i.e
4<->8<->9<->7<->K<->6<->3
now keep repeating it for the Element which are not the min. And stop when only king remains.

But I am not sure about the time. Can somebody tell me if this approach is correct or not.if it is what will be the time complexity

thanks in advance

l = [];
for x in range(13):     
    i =  (13-x)%(x+1);
    l.insert(0,13-x);
    l = l[-i:] + l[:-i];

print l

(n(n+1)/2 + (n-1))%13 is the index

Take an array of 13 elements set to zero.

for each n (n < 7) skip n zeros and set the next field to n. for n > 6 skip 12-7 zeros and set the next zero element to the value.

-- After removing 6 elements there wont be more than 6 elements to move down to place the last element. (6+6+1).

Take an array of 13 elements set to zero.

for each n (n < 7) skip n zeros and set the next field to n. for n > 6 skip 12-7 zeros and set the next zero element to the value.

-- After removing 6 elements there wont be more than 6 elements to move down to place the last element. (6+6+1).

I think this is the modified Josephus permutation problem with the k being not constant. If k is supposed to be constant it is linear solution problem. We need to use augmented balanced binary search tree with extra field (this field is left sub-tree size and right sub-tree size) in it to get the best next indexed empty slot in the array. This is really very interesting problem. So the complexity analysis goes like this.
First the construction of the augmented binary search tree for all 13 elements in O(nlogn). Then we iterate in loop for each element, we pick the empty slot of particular index from BST which is O(logn). So for n elements it is O(nlogn). I guess this is the solution for it.

Use List structure in java to avoid rotation

public int[] arrangeCards(int n) {
	List<Integer> list = new ArrayList<Integer>();
	int pos = 0;
	for(int i = n ; i > 0; i--) {
		list.add(pos, i);
		pos -= i % (n - i + 1);
		pos = (pos + (n - i + 1)) % (n - i + 1);
	}
	int[] array = new int[list.size()];
	for(int i = 0; i < list.size(); i++) {
		array[i] = list.get(pos);
		pos = (pos + 1 + n) % n;
	}
	return array;
}

#include "stdio.h"
#include "stdlib.h"

#define NUM 13

/* GLOBAL STRUCTURE */
typedef struct Stack Stack;

struct Stack
{
int id;
Stack* next;
Stack* prev;
};

/* GLOBAL VARIABLE */
Stack* top = NULL;
Stack* bot = NULL;

/* GLOBAL FUNCTIONS */
void ArrangeCards(void)
{

int i;
Stack* temp;

	for(i=NUM; i>0; i--)
	{
	temp = (Stack*)malloc(sizeof(Stack));
	temp->id = i;
	
		if(top == NULL)
		{
			temp->next = NULL;
			temp->prev = NULL;

			top = temp;
			bot = temp;
		}
		else
		{
			int j; //Num of times bot to top
			Stack* iter;
			
			/* Place new card on Top */
			temp->next = top;
			temp->prev = NULL;
			
			top->prev = temp;

			top = temp;

			/* Shuffle card */
			j = i%(NUM - i + 1);
			for(;j>0;j--)
			{
			//Remove from bottom put it on top
			iter = bot;

			bot = bot->prev;
			bot->next = NULL;

			iter->next = top;
			iter->prev = NULL;

			top->prev = iter;
			top = iter;
			}
		}
	}
}

/* MAIN FUNCTION */
int main()
{
Stack* temp;

ArrangeCards();

temp = top;
printf("Card sequence : \n");
while(temp)
{
printf(" %d ", temp->id);
temp = temp->next;
}

printf("\n");

return 0;
}

Output :

rajkamal@Rajkamal-PC:~/Documents/Junk$ ./CardSeq.o
Card sequence :
4 1 13 11 2 10 6 7 3 5 12 9 8


I used modulo to reduce numer of iterations .. but will it be O(nlogn) ??

void arrangeCard(int a[], int n) { //here n = 13
	//Assuming  array a[] is initialised with value zero at all index.
	int index = 0;
	int count, k;
	for(int i = 0; i < 13; i++) {
		count = i+1;
		k = 0;
		while( k <= count) { 
			if( a[i] == 0) {
				k++;
			}
			index = (index + 1)%n;  // n=13 in this case
		}
		a[index++] = i;
	}

}

{
public class Test {
public static void main(String[] args) {
int[] arr = new int[13];
int index;
for (index = 0; index < 13; index ++) {
arr[index] = 0;
}

int card = 1;
index = 0;
while (card <= 13) {
int skip = 0;
while (skip < card) {
if (arr[index] == 0) {
skip ++;
}
index = (++index) % 13;
}

while (arr[index] != 0) index = (++index) % 13;
arr[index] = card ++;
}
for(index=0; index < 13; index++) System.out.print(arr[index] + ", ");
}

}
}