Problem:


Problem F: nCm

Problem

  整数nが与えられた時、nCm(異なるn個のものからm個を選ぶ組み合わせの数)が偶数となるような最小のmを出力せよ。

Input

入力は以下の形式で与えられる。

n

Constraints

入力は以下の条件を満たす。

    
1 ≤ n ≤ 1018

Output

   nCmが偶数となるような最小のmを1行に出力する。

Sample Input 1

2

Sample Output 1

1

Sample Input 2

111

Sample Output 2

16

Sample Input 3

3

Sample Output 3

4



Sample input:
2


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
def nCm(n, k):
    C = [1] + [0 for i in range(1, k+1)]
    for i in range(1, n+1):
        j = min(i, k)
        while j > 0:
            C[j] += C[j-1]
            j -= 1
    return C[k]

n = int(input())
k = 1
while nCm(n, k) % 2:
    k += 1
print(k)

Submission status: Accepted

Solution code:
n = int(input())
print((n+1) &- (n+1))

Submission status: Accepted

Solution code:
n = int(input()) + 1
print(n &- n)

Submission status: Accepted

Solution code:
n=int(input())+1;print(n&-~~n)