카드2

• 카드1에서 N의 범위를 늘리고, 마지막 남는 카드만 출력하게 변형한 문제.
• N이 늘어났지만, 그래도 최대 500,000 이기 때문에 deque를 사용해서 O(n)에 구현해도 여유있게 풀리기는 한다.
• 그러나 이 문제에서 카드를 조작하는 것이 요세푸스 문제와 같은 패턴이고, 전체 시퀀스가 아니라 마지막에 남는 카드만 출력하면 되기 때문에, 요세푸스 문제에서 설명한 효율적인 방법을 적용할 수 있다.
  • 여기에서는 k=2이므로, 그냥 공식에 바로 대입해서 풀 수 있다.
    • $ J_{n,2} = 1+2(n-2^{\lfloor{log_{2}n}\rfloor}) $
    • 요세푸스 문제에서는 처음으로 제거하는 수가 2가 된다. 윗 공식의 J(n,2)도 그 경우에 마지막으로 남는 수를 찾는 공식이다. 이 문제에서는 요세푸스 문제와 달리 처음 제거하는 수가 1이다. 그래서 위의 공식에서 구한 J(n,2)에서 1을 뺀 값을 답으로 출력하면 된다. 만약 그 값이 0이 되는 경우에는 (N=2^x인 경우), N을 대신 답으로 출력해주면 된다.
    • 이렇게 하면 시간복잡도는 O(1)

"""Solution code for "BOJ 2164. 카드2".

- Problem link: https://www.acmicpc.net/problem/2164
- Solution link: http://www.teferi.net/ps/problems/boj/2164
"""


def main():
    N = int(input())  
    answer = ~(1 << N.bit_length()) & (N << 1)
    if answer == 0:
        answer = N
    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 2164. 카드2".

- Problem link: https://www.acmicpc.net/problem/2164
- Solution link: http://www.teferi.net/ps/problems/boj/2164
"""

import collections


def main():
    N = int(input())
    deq = collections.deque(range(1, N + 1))
    while deq:
        discarded_card = deq.popleft()
        deq.rotate(-1)
    print(discarded_card)


if __name__ == '__main__':
    main()