OA | AMAZON SDE 2

The engineers at Amazon are working on a new rating system for their products. For each product, an array customer_rating is maintained for the last n orders of that product, where the rating given by the ith customer is represented by customer_rating[i].

The following algorithm is used to calculate the new_rating of the product:

The engineers can perform the following operation to the array customer_rating at most k times:

Choose a customer rating and add 1 to that.

The new_rating is the maximum Bitwise AND of any m-sized subset of the array customer_rating.

Given n customer ratings, two integers m and k, and an array customer_rating, find the maximum possible new_rating of the product by performing the operations optimally.

Example

Given n = 4, k = 8, m = 2 and
customer_rating = [1, 2, 4, 8].

One of the optimal ways is explained below:

Apply the operation on customer_rating[3] 6 times
Apply the operation on customer_rating[4] 2 times


The optimal subset of size 2 is [10, 10] with a Bitwise AND of 10.

Note that there could also be other possible modifications of the array customer_rating, for example:
customer_rating = [1, 2, 4, 16] (All the operations performed on the last element).
However, the optimal m-sized subset in this case can be any two elements with the same Bitwise AND of 0.

It is guaranteed that there is no other possible modification of the array customer_rating that results in yielding the Bitwise AND of m-sized subset greater than 10.

Hence, the maximum possible new_rating is 10.


1 ≤ n ≤ 10^5
1 ≤ customer_rating[i] ≤ 10^9
1 ≤ k ≤ 10^9
1 ≤ m ≤ n


STDIN FUNCTION
3 → customer_rating[] size n = 3
1 1 1 → customer_rating = [1, 1, 1]
3 → k = 3
3 → m = 3

2


STDIN FUNCTION
3 → customer_rating[] size n = 3
1 3 2 → customer_rating = [1, 3, 2]
5 → k = 5
1 → m = 1

8