Rising Chain With Shared Bits

Medium

You get two positive integers count and mask. Build a strictly increasing sequence of count positive integers whose bitwise AND (&) over all elements is exactly mask. Return the smallest possible value of the last element of such a sequence.

Example 1

count=3, mask=5 → 13

The chain [5, 7, 13] works: 5 & 7 & 13 = 5. No chain ends lower.

Example 2

count=4, mask=2 → 7

The chain [2, 3, 6, 7]: every number has the bit 2 and no other bit is shared by all of them.

Example 3

count=1, mask=6 → 6

Constraints

1 ≤ count ≤ 10⁹
1 ≤ mask ≤ 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation

Similar problems

Division Without Dividing Medium Every Topping Combo Medium Mirrored One-Bit Codes Medium All Distinct Card Hands Medium The Odd One Among Triples Medium

Input

count=3, mask=5

Expected

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