Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shrink the Array

By fsshakkhor · Limits 500ms, 256 MB

You have an array of size N which contains positive integers. You can apply the following operation on the array.

  • You select an index i (1 ≤ i < size_of_current_array).
  • Apply A[i + 1] = A[i + 1] XOR A[i].
  • Remove the i'th element from the array.

You have to apply this operation exactly K times on the array. Finally, you will get an array of size (N - K). You have to minimize the maximum element of the final array.


The first line contains two integers N (2 ≤ N ≤ 50000) and K (1 ≤ K < min(51,N)).

The next line contains N integers Ai (1 ≤ Ai ≤ 109), denoting the elements of the array.


Print the answer in a single line.


3 1
1 2 3

If we pick i = 1, we will get [1, 3, 3]. After removal of first element the array will become [3, 3]. Maximum element is 3.

If we pick i = 2, we will get [1, 2, 1]. After removal of second element the array will become [1, 1]. Maximum element is 1.

So, the answer is 1.



37% Solution Ratio

tmwilliamlin168Earliest, Feb '20

chieloFastest, 0.1s

Andres_UntLightest, 10 MB

tmwilliamlin168Shortest, 564B


Login to submit


This problem can be solved using dynamic programming. Our DP will have two parameters—position and n...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.