All Tracks>Algorithms> Searching> Binary Search> Problem
Optimal Division
★★★★★

5

2 votes
, Binary Search, Algorithms
Problem

You have an array A of length N. You have to divide the array into atmost M consecutive segments such that the maximum bitwise OR of these segments is minimum.

Find the minimum possible maximum Bitwise OR of these segments if you divide optimally.

Input Format:

  • The first line contains an integer T, denoting the number of test cases.
  • The first line contains two integers, N and M.
  • The next line contains N space-separated integers, elements of array A.

Output Format:

For each test case, print the minimum possible maximum Bitwise OR of these segments if you divide optimally.

Constraints:

1≤T≤101≤M≤N≤1051≤A[i]≤109

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

First test case:
We can divide A into [4]. Bitwise OR of these segments is 4. Hence, the answer is 4, which is the minimum possible.

Second test case:
We can divide A into [12,9] and [7]. Bitwise OR of these segments is 13,7. Hence, the answer is 13, which is the minimum possible.

Editor Image

?