Back
Close
  • 100

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

 Goal

You have N cards in a stack. Each card has a different number written on it.

The top card is written 1. The second card is written 2. The third card is written 3...
The sequence continues to the last card (the bottom card) which is written N.

Repeat the following operations until the stack of cards is reduced to 1 card:
➀ throw away the top card
② move the current top card to the bottom

You got one last card in hand. What is the number written on it?
Input
Line 1: an integer N
Output
Line 1: the number on the remaining card
Constraints
1 ≤ N ≤ 1,000,000,000

Be aware of the very high upper limit. Design a fast algorithm to solve it.
Example
Input
6
Output
4

A higher resolution is required to access the IDE