A row of antique combination vaults each has a rotating dial marked with consecutive non-negative integers. Turning the dial from some starting position x up through the vault's current reading n (visiting every integer x, x+1, ..., n along the way) and taking the bitwise AND of every position visited produces the vault's "reset signature." A vault only pops open when that signature is exactly 0. For each vault, given only its current reading n, find the largest starting position x (with 0 <= x <= n) that would have produced a reset signature of 0.
q, the number of vaults.q integers n[1..q], the current reading of each vault.Print q integers separated by single spaces on one line: for each vault, the largest valid starting position x.
Example 1
Input
2 7 9
Expected
3 7
Explanation
For a reading of 7, turning the dial from 3 through 7 ANDs to 0 (3&4&5&6&7=0), and no larger starting position works (e.g. 5&6&7=4), so the answer is 3. For a reading of 9, turning the dial from 7 through 9 ANDs to 0 (7&8&9=0), and no larger starting position works (8&9=8), so the answer is 7.
Example 2
Input
3 1 2 3
Expected
0 1 1
Explanation
For a reading of 1, only x=0 zeroes the signature (0&1=0, while starting at 1 alone gives 1). For a reading of 2, starting at 1 gives 1&2=0, while starting at 2 alone gives 2, so the answer is 1. For a reading of 3, starting at 1 gives 1&2&3=0, while starting at 2 gives 2&3=2, so the answer is 1.
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 →