Smallest Unreachable OR

Medium

You get an array of positive integers values. Call a number x reachable if you can pick a non-empty set of elements of the array (each at most once) whose bitwise OR is exactly x. Return the smallest positive integer that is not reachable.

Example 1

values=[1, 2, 6] → 4

You can get 1, 2, 3 = 1 | 2, 6 and 7 = 1 | 6. But 4 is out of reach: the only value with the 4s bit set is 6, and any OR including it is at least 6.

Example 2

values=[3, 5] → 1

Even 1 is unreachable: the array has no 1, and every OR is at least 3.

Example 3

values=[4, 1, 2, 8, 9] → 16

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Brainteaser Array

Similar problems

Take From Any Pile Medium Longest Stretch with the Top AND Medium XOR of Every Cross Pair Medium OR of All Subset Sums Medium XOR Tile Duel Hard

Input

values=[1, 2, 6]

Expected

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.