해설
bitwise OR 연산은 한 번 1이 된 비트를 다시 0으로 만들 수 없다. 따라서 에서 이미 1인 비트는 에서도 반드시 1이어야 한다. 즉, 가 필요하다.
또한 어떤 버튼 를 눌렀을 때 에 에 없는 비트가 포함되어 있으면, 그 비트가 켜져서 최종적으로 가 될 수 없다. 따라서 사용할 수 있는 버튼은 를 만족하는 버튼뿐이다.
이제 에는 1이지만 에는 0인 각 비트를 켜야 한다. 각 비트에 대해, 그 비트를 포함하면서 를 만족하는 버튼이 하나라도 있으면 그 버튼을 누르면 된다.
정수의 범위가 이하이므로 확인해야 할 비트는 30개 정도뿐이다. 각 버튼을 보면서 각 비트를 켤 수 있는 버튼 하나를 저장하면 에 해결할 수 있다.
선택한 버튼 수는 필요한 비트 수 이하이므로 최대 30개이고, 따라서 100번 제한을 항상 만족한다.