How to solve this problem asked in Coding interview?

Revision en1, by Agent_Lemon, 2022-01-25 23:11:08

You are given an array of N numbers. The game goes like this. You have to select any two elements P and Q from the array. The cost of selecting these two elements will be (P | Q — P & Q) where "|" denotes the bitwise OR of two numbers and "&" denotes the bitwise AND of two numbers. Now out of these two numbers, throw one number and put the other number back into the array.

This way the size of the array will get reduced by one element. The game stops when there is only one element left in the array. The total cost of reducing the array to a single element is the sum of the costs incurred in all the steps.

Now, your task is to reduce the array to a single element while minimizing the total cost incurred.

Constraints:

1 <= N <= 10^3

1 <= A[i] <= 10^3

Tags interview, hevi problem, coding rounds

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Agent_Lemon 2022-01-25 23:11:08 863 Initial revision (published)