Maximum OR | Practice Problems

Maximum OR

★★★★★

3.2

9 votes

Bit Manipulation, Basic Programming, Basics of Bit Manipulation, Algorithms

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ containing $N$ integers. You can do the following operation at most $K$ times:

Choose any index $i$ and increase the value of $A_i$ by $1$ .

Your task is to find the maximum bitwise OR of the array.

Input format

The first line contains an integer $T$ denoting the number of test cases.
The first line of each test case contains two space-separated integers $N$ and $K$ .
The second line of each test case contains $N$ space-separated integers denoting array $A$ .

Output format

For each test case, print the maximum possible bitwise OR of the array after performing at most $K$ operations in a new line.

Constraints

$1 \le T \le 100000\\ 1 \le N \le 200000\\ 0 \le K \le 1e18\\ 0 \le A_i \le 2^{60}$

It is guaranteed that the sum of $N$ over $T$ test cases does not exceed $1e6$ .

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For the first testcase, we can increase the value of $5$ -th index by $2$ . Thus the $A$ becomes {}. The bitwise OR of the array $A$ becomes $15$ .

For the second testcase, we can increase the value of $1$ -th index by $1000000000$ . Thus the $A$ become { $1000000000$ }. The bitwise OR of the array $A$ becomes $1000000000$ .