Remaining Card
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
Tags
Sequences
Difficulty
Medium
Test cases
Example Test
Input
6
Output
4
Validator, example Validator
Input
5
Output
2
Easy Test
Input
15
Output
14
Validator, easy Validator
Input
13
Output
10
A little more Test
Input
32
Output
32
Validator, more Validator
Input
64
Output
64
A thick deck Test
Input
777
Output
530
Validator, thicker Validator
Input
369
Output
226
Heavy deck Test
Input
9876
Output
3368
Validator, heavy Validator
Input
1490
Output
932
Getting serious Test
Input
609901
Output
171226
Validator, serious Validator
Input
997301
Output
946026
Millions 1 Test
Input
566373192
Output
59004560
Validator, M1 Validator
Input
449020768
Output
361170624
Millions 2 Test
Input
697691238
Output
321640652
Validator, M2 Validator
Input
136038216
Output
3640976
Ultimate test Test
Input
1000000000
Output
926258176
Validator, ultimate Validator
Input
999999993
Output
926258162
Boundary case Test
Input
1
Output
1
Validator, boundary Validator
Input
2
Output
2
Solution language
Solution
Stub generator input