비밀번호 제작

면접 대비

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

요약

N과 이미 사용된 M개의 암호가 주어질 때, 0부터 N까지의 값 중 사용된 암호까지의 최소 해밍 거리를 가장 크게 하는 값을 찾는다.

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

문제

서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받았다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부된 파일에는 지금까지 로그인 시도에 사용된 비밀번호 목록이 있었다. 서버 관리자 계정의 비밀번호로는 $0$ 이상 $N$ 이하의 정수 중 하나를 사용할 수 있다.

두 비밀번호의 안전 거리는 이진법으로 표현한 두 비밀번호의 서로 다른 자리의 개수로 정의한다. 예를 들어 $3$ 을 이진법으로 표현하면 $0011$ , $8$ 을 이진법으로 표현하면 $1000$ 이 되고, 서로 다른 자리의 개수는 $3$ 개이므로 $3$ 과 $8$ 의 안전 거리는 $3$ 이 된다.

어떤 비밀번호의 안전도는 지금까지 로그인 시도에 사용된 모든 비밀번호와의 안전 거리 중 최솟값으로 정의한다. 예를 들어 지금까지 로그인 시도에 사용된 비밀번호가 $3$ 과 $4$ 라고 가정하면, 새로운 비밀번호 $8$ 에 대해 $3$ 과 $8$ 의 안전 거리는 $3$ , $4$ 와 $8$ 의 안전 거리는 $2$ 이므로 비밀번호 $8$ 의 안전도는 $2$ 가 된다.

향빈이는 해커가 비밀번호를 알아내기까지의 시간을 최대한 늦추기 위해 현재 사용 중인 관리자 계정 비밀번호의 안전도가 가장 높게끔 바꾸고 싶다. 이때, 안전도가 제일 높은 비밀번호의 안전도를 구하여라.

입력

첫째 줄에 관리자 계정 비밀번호의 최댓값을 나타내는 정수 $N$ 이 주어진다. ( $0 \leq N \leq 1\ 000\ 000$ )

둘째 줄에는 로그인 시도에 사용된 비밀번호의 개수를 나타내는 정수 $M$ 이 주어진다. ( $1 \leq M \leq 100\ 000$ )

셋째 줄에는 로그인 시도에 사용된 비밀번호 값인 정수 $p_1, p_2, \cdots, p_M$ 이 주어진다. ( $0 \leq p_i \leq N$ )

출력

안전도가 제일 높은 비밀번호의 안전도를 출력한다.

예제1

예제 1
입력
```
10
2
3 4
```
예상 출력
```
2
```