MEX-OR solution codechef

• For Solution

  Click Here!

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of [2,2,1][2,2,1] is 00, because 00 does not belong to the array.
• The MEX of [3,1,0,1][3,1,0,1] is 22, because 00 and 11 belong to the array, but 22 does not.
• The MEX of [0,3,1,2][0,3,1,2] is 4 because 0,1,20,1,2 and 33 belong to the array, but 44 does not.

Find the maximum possible MEX of an array of non-negative integers such that the bitwise OR of the elements in the array does not exceed XX.

MEX-OR solution codechef

• The first line contains TT denoting the number of test cases. Then the test cases follow.
• Each test case contains a single integer XX on a single line.

Output Format

For each test case, output on a single line the maximum possible MEX of the array satisfying the given property.

MEX-OR solution codechef

• 1≤T≤1051≤T≤105
• 0≤X≤1090≤X≤109

Subtasks

Subtask 1 (100 points): Original constraints

MEX-OR solution codechef

 

4
0
1
2
5

MEX-OR solution codechef Output 1 

1
2
2
4

Explanation

Test case 11: The array could be [0][0].

Test case 22: The array could be [0,1][0,1]. Here the bitwise OR of 00 and 11 is 11 and the MEX of the array is 22 as both 00 and 11 belongs to the array.

Test case 44: The array could be [1,0,3,2][1,0,3,2]. Here the bitwise OR of all integers in the array is 33 and the MEX of the array is 44.

• For Solution

  Click Here!