First Trial

At each step we discard a card away, and move the new card at the top to the bottom of the deck. That suggests we eliminate half of the deck for one iteration. Consider the following deck

1x
2->
3x
4->
5x
6->
7x
8->

Here, We have a deck of eight cards whereby card number one is at the top of the deck. x indicates the card is to be thrown away, while -> indicates the card to be moved to the bottom. Note that in this case, None of the -> cards are going to be thrown away due to later x. It is easy to see that the result is as follows

2
4
6
8

Similarly to the first iteration, the second one would be

2x
4->
6x
8->

yielding

4
8

Finally, Getting card eight as the answer.

So, On each iteration, we divided the dick by half and still got an even number of cards. It is clear that is attributed to the fact that eight is a power of two. Otherwise, On some iteration we would end-up with an odd number of cards. That iteration is not the last one in which we have the last remaining card. You could see if we have a deck whose cards number is some power of two, Then the answer would be the last card at the bottom. In other words, if our cards number is $n = 2^k$ for some k, Then the correct answer of the problem, i.e the last remaining card after discarding cards and moving them to the bottom, is $2^k$.

More Justification of First Trial’s Observation

Let’s try to take a deeper look at why do we always obtain the last bottom card as the remaining one in case the deck is some power of two, As illustrated earlier. Consider our $2^3 = 8$ deck but represented differently

On First Iteration:

$2^0 \times 1$x
$2^0 \times 2$->
$2^0 \times 3$x
$2^0 \times 4$->
$2^0 \times 5$x
$2^0 \times 6$->
$2^0 \times 7$x
$2^0 \times 8$->

On Second Iteration:

$2^1 \times 1$x
$2^1 \times 2$->
$2^1 \times 3$x
$2^1 \times 4$->

On Third Iteration:

$2^2 \times 1$x
$2^2 \times 2$->

Remarkably, Cards multiplied by an odd number gets thrown away, while cards multiplied by an even number gets moved to the bottom and survives to the next iteration. You could also see that $2^{k_0} \times (2k_1) = 2^{k_0+1}$. The even number increases the power of two by one. That correspoinds with our observation that each iteration’s power is increased by one than its predocessor’s power. Clearly, Continuing in this way ends us up with the greatest power of two in the whole deck, which is also the last bottom card.

Generalizing for None Power of Two

Our solution for the generalized case is in fact an extension of the special case of deck’s whose number is a power of two. Let’s begin from where we ended up.

A Deck of Seven Cards

On First Iteration:

1x
2->
3x
4->
5x
6->
7

Note that I intentionally did not mark card seven. Otherwise, The second iteration would have the first card marked as ->, violating consistency of marking among iterations. In case cards number is odd, as in this case, We prefer to avoid marking the last card, and get the second iteration as

7x
2->
4x
6->

We have got here cards of some power of two. Following our illustrated observation in the previous section, We could conclude the last remaining card is card six.

For eight cards deck, The second iteration was <2, 4, 6, 8>. Removing card eight from the deck resulted in having card seven as a remainder from the first iteration, and shifting <2, 4, 6, 8> one position to the right. As a result, We have card six as the last one in second iteration

For eight cards deck, The last remaining card was eight. For seven cards deck, the last remaining card is six. Removing one card from the eight cards deck yielded the same remaining card but subtracted by two. In other words, $8 - 1$ cards deck yields the last remaining card sevenCardsAnswer = eightCardsAnswer - (2 * removedCards) = 8 - (2 * 1) = 6. Let’s try more trials and see how they relate with the case of eight cards deck

A Deck of Six Cards

On First Iteration:

1x
2->
3x
4->
5x
6->

On Second Iteration:

2x
4->
6x

So, we end-up with card four. Again, $8 - 2$ cards deck yields the last remaining card sixCardsAnswer = eightCardsAnswer - (2 * removedCards) = 8 - (2 * 2) = 4. Here, unlike the case of seven cards deck, There is no remainder from the first iteration so that we end up with four cards in the second iteration. As two cards are removed from eight cards deck, we have three cards in second iteration rather than four. card six here is in an odd position, so it gets thrown away. The last remaining card is card four. In other words, It seems removing two cards from eight cards deck shifted our <2, 4, 6, 8> a position to the right in addition to removing the last card.

A Deck of Five Cards

On First Iteration:

1x
2->
3x
4->
5

As in the case of seven cards deck, We do not mark card five in the first iteration. Recall the the last card is not marked whenever we have an odd number of cards in an interation.

On Second Iteration:

5x
2->
4x

Again, $8 - 3$ cards deck yields the last remaining card fiveCardsAnswer = eightCardsAnswer - (2 * removedCards) = 8 - (2 * 3) = 2. It seems removing two cards shifted <2, 4, 6, 8> on position to the right, and removing an additional card shifted it another position to the right but with a remainder, namely card five. So, we get card two as the answer.

Magical Formula

The illustrated reasoning SEEMS to work on not just $2^3 = 8$ but any power of two. For an arbitrary number of deck cards $n$, We find the power of two greater than or equal to $n$, Then compute the answer for $n$ by nCardsAnswer = Power2CardsAnswer - (2 * (Power2Cards - nCards)). So, How do find the power of two equal or greater than $n$? Here is a trick: $2^{ceil(log_2(n))}$. So, The final formula would be

$$2^{ceil(log_2(n))} - (2 \times (2^{ceil(log_2(n))} - n)) = 2 \times (n-2^{ceil(log_2(n))-1})$$

Accepted Source Code on UVa

#include &lt;cstdio&gt;
#include &lt;math.h&gt;

using namespace std;

int main() {
  int n, res;

  scanf("%d", &amp;n);

  res = 2*(n-pow(2, (ceil(log2(n))-1)));
  
  if (n == 1) printf("1\n");
  else printf("%d\n", res);
  
  return 0;
}