Optimal Way

3.2

4 votes
Datastructures, Algorithms, Dynamic Programming, Introduction to Dynamic Programming 1, Bitmask
Problem

You are provided an array Arr of non-negative integers of size 2K. In each round, pick any two integers from the array Arr (number1 and number2) and then eliminate both of them. 
The formula for your score in each round is = RoundNumber(number1&number2).
RoundNumber will start from 1 till K, and "number1&number2" represents bitwise AND of number1 and number2. The total number of rounds is K. The sum of the scores you will receive in each round will represent your final score. Return the maximum possible final score. 

Input Format:

  • The first line contains an integer N, where N denotes the size of the array Arr.
  • The second line contains an interger K.

Output Format:

  • Print the maximum possible final score.

Constraints:

  • 1K10
  • 1N20
  • 1Arr[i]107
  • N=2K

 

Sample Input
4
3 4 5 9
2
Sample Output
9
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

Example: K = 2, H = [3,4,5,9]. 
RoundNumber = 1, choose {3,9}, Score = 1*(3&9) = 1*(1) = 1.
RoundNumber = 2, choose {4,5}, Score = 2*(4&5) = 2*(4) = 8.
Final score = 1 + 8 = 9. The maximum possible final score is 9. 

Editor Image

?