A coastal watch station manages n signal beacons. Each beacon is permanently wired to broadcast one fixed positive integer code. At any time, the station operator may activate any non-empty group of beacons; when a group is activated, the combined transmission sent out over the wire is the bitwise OR of the activated beacons' codes. Because different groups can be chosen, many positive integers can be produced this way -- but some never can, no matter which beacons are grouped together.
Given the beacon codes, find the smallest positive integer that cannot be produced as the bitwise OR of any non-empty subset of them.
n, the number of beacons.n space-separated integers, the beacon codes.A single integer: the smallest positive integer that is not achievable as the bitwise OR of any non-empty subset of the beacon codes.
Example 1
Input
2 2 1
Expected
4
Explanation
Beacons carry codes 2 and 1. The possible non-empty groups give OR values 2, 1, and 2|1=3, so every integer from 1 through 3 is reachable. The value 4 can never be produced by any subset, so it is the answer.
Example 2
Input
3 5 3 2
Expected
1
Explanation
None of the beacon codes equals 1, and OR-ing any non-empty subset of values that are each at least 2 can only add bits, never shrink the result below the largest value used -- so no group can ever OR down to exactly 1. Since 1 is already unreachable, it is the answer.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →