Problem :

https://www.hackerrank.com/challenges/sum-vs-xor/problem


My Solution :

#!/usr/bin/env python3


def sum_xor(n):
return 1 if n == 0 else 2**(bin(n).count('0')-1)


n = int(input().strip())
result = sum_xor(n)
print(result)


Comment :

단순 반복으로 대입해서 풀면 Timeout이 발생할 수 밖에 없다. 0 <= n <= 10**15 이니 엄청 큰 숫자가 입력으로 들어올 것이기 때문이다.


규칙을 발견하고자 임의의 수 84를 가지고 아래와 같이 정리하다 보니 규칙이 눈에 들어왔다.



내가 발견한 규칙은 아래와 같다.


x를 0부터 증가시키면서 대입해본 결과


1. sum과 xor가 같은 값이 나오려면 m의 이진 자리수가 0일 때만 의미가 있다.


2. 0을 제외한 각 단계별 갯수가 1 -> 2 -> 4 -> 8 이렇게 증가함을 발견하였다.


따라서 m을 이진수로 표현한 후 0의 갯수를 세어 2 ** (0의 갯수) 해주면 정답이 나온다. 단 m이 0일 때는 2**1 == 2로 오답이 되므로 1을 리턴해야 한다.