### PROBLEM LINK:

**Author:** Mahmoud Badawy

**Tester:** Mohammed Ehab

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Greedy, Sorting

### PROBLEM:

Given two arrays A and B and a number k you have to replace exactly k elements from A with their XOR value with B find the maximum sum you can get

### QUICK EXPLANATION:

Sort the elements by their A[i]^B[i]-A[i] and chose the best K

### EXPLANATION:

If you used a magic spell on the i-th element it will increase the sum by A[i]^B[i]-A[i] so you can find the best K elements which will increase your sum and use the magic spells on them

Complexity : O(n*log(n))

Score: 100 points

### ALTERNATIVE SOLUTION:

You can use dynamic programming where dp[i][j]=maximum sum in the first i elements if you used j magic spells on them and the answer will be in dp[n][k]

Complexity : O(n*k)

Score: 50 points

### AUTHORâ€™S SOLUTIONS:

greedy solution can be found here (100 point).

DP solution can be found here (50 point).