Skip to main content
Computer Science

Return to Question

edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
deleted 12 characters in body
Source Link
HimalayanCoder
HimalayanCoder
  • 111
  • 6

We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

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

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

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

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

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

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

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

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

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

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

2 3 1 4 
1 2 3 4

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2

Source Link
HimalayanCoder
HimalayanCoder
  • 111
  • 6

Sort deck of cards with least no of moves

We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

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

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

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

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2