FastPrep
Problem · Array

Maximum Product New Rating

● HardAmazonNEW GRADOA
See Amazon hiring insights

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 i-th 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.

Examples
01 · Example 1
customer_rating = [1, 2, 4, 8]
m = 2
k = 8
return = 10

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

One of the optimal ways is explained below:

start
1248
↓
Apply the operation on customer_rating[3] 6 times
after 6 operations
12108
↓
Apply the operation on customer_rating[4] 2 times
after 8 operations
121010
  • Apply the operation on customer_rating[3] 6 times to get customer_rating = [1, 2, 10, 8].
  • Apply the operation on customer_rating[4] 2 times to get customer_rating = [1, 2, 10, 10].

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 operation performed on the last element). However, the optimal m-sized subset in this case can be any two elements all with 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 an m-sized subset greater than 10.

More Amazon problems
drafts saved locally
public int getMaximumNewRating(int[] customer_rating, int m, int k) {
  // write your code here
}
customer_rating[1, 2, 4, 8]
m2
k8
expected10
checking account