Optimal Way
Practice
3.2 (4 votes)
Datastructures
Algorithms
Dynamic programming
Introduction to dynamic programming 1
Bitmask
Problem
90% Success 1020 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

You are provided an array Arr of non-negative integers of size 2∗K. 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:

  • 1≤K≤10
  • 1≤N≤20
  • 1≤Arr[i]≤107
  • N=2∗K

Sample Input
4
3 4 5 9
2
Sample Output
9
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.

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Submissions
Please login to view your submissions
Similar Problems
Points:30
12 votes
Tags:
Introduction to Dynamic Programming 1BitmaskDynamic ProgrammingAlgorithms
Points:30
7 votes
Tags:
AlgorithmsC++Dynamic Programming
Points:30
1 votes
Tags:
Max subarray sumIntroduction to Dynamic Programming 1Dynamic ProgrammingAlgorithms
Editorial

Login to unlock the editorial