사탕 나누기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

사탕 개수가 2의 거듭제곱인 상자 N개를 두 그룹으로 나눠, 양쪽 합이 모두 2의 거듭제곱이 되도록 할 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 수학, 그리디, 정렬, 비트 연산
정답자: 아직 제출이 없습니다

문제

Bob과 Charlie는 2의 거듭제곱을 무척 좋아하는 두 형제다. 두 사람의 어머니는 사탕 상자 N개를 주기로 했고, 상자마다 들어 있는 사탕 개수는 2의 거듭제곱이다.

두 형제는 상자를 나누려고 한다. 각 상자를 누가 가질지 정하되, 모든 상자는 정확히 한 사람에게만 주어진다.

이때 두 형제 각자가 받는 사탕 개수의 합도 2의 거듭제곱이 되도록 나눌 수 있을까?

예를 들어 N = 4이고 상자에 4, 4, 32, 8개의 사탕이 들어 있다면 답은 yes다. 세 번째 상자를 Bob에게 주고(사탕 32개), 나머지 상자를 Charlie에게 주면(4 + 4 + 8 = 16개) 되기 때문이다.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 105)이 주어진다. 이는 형제가 나누려는 상자의 개수다. 둘째 줄에 N개의 정수 A1, A2, . . . , AN (0 ≤ Ai ≤ 105, i = 1, 2, . . . , N)이 주어지며, i번째 상자에 2Ai개의 사탕이 들어 있음을 뜻한다.

출력

두 형제가 받는 사탕 개수의 합이 각각 2의 거듭제곱이 되도록 상자를 나눌 수 있으면 대문자 “Y”를, 그렇지 않으면 대문자 “N”을 한 줄에 출력한다.

예제4

예제 1
입력
```
4
2 2 5 3
```
예상 출력
```
Y
```
예제 2
입력
```
1
42
```
예상 출력
```
N
```
예제 3
입력
```
5
3 1 4 1 5
```
예상 출력
```
N
```
예제 4
입력
```
7
0 0 1 2 3 4 5
```
예상 출력
```
Y
```