R01448
최대 XOR 쌍
골드 IV레이팅
의견: 0
설명
암호 연구소의 컴퓨터에는 \(N\)개의 비음수 정수 \(a_1, a_2, \ldots, a_N\)이 저장되어 있다.
서로 다른 두 인덱스 \(i\), \(j\) (\(i \ne j\))를 골라 \(a_i \oplus a_j\)의 최댓값을 구하여라. 여기서 \(\oplus\)는 비트 XOR 연산이다.
제약
- \(2 \le N \le 200\,000\)
- \(0 \le a_i < 2^{30}\) (\(\approx 10^9\))
입력 형식
첫째 줄에 정수의 개수 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 비음수 정수 \(a_1, a_2, \ldots, a_N\)이 공백으로 구분되어 주어진다.
출력 형식
\(a_i \oplus a_j\)의 최댓값을 출력한다.
예제 1
입력
6
3 10 5 25 2 8
출력
28
설명
두 수 \(5\)와 \(25\)의 XOR는 \(5 \oplus 25 = 28\)이고, \(2\)와 \(25\)의 XOR는 \(2 \oplus 25 = 27\)이다. 가능한 쌍 중 최댓값은 \(5 \oplus 25 = 28\)이다.
예제 2
입력
4
0 0 1 1
출력
1
설명
\(0 \oplus 1 = 1\)이 최대이다. 같은 값끼리의 XOR는 \(0\)이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
최대 XOR 쌍
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최대 XOR 쌍
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기