XOR DARE

We can recursively try out all the possible subsets of the array. We have two options for every element of the array: either to take it in the subset or not. We call the recursive function for both of the cases and take the best of them. 

We can keep the current strength in the recursive function and update it according to our choices in the subsequent calls.

When we reach the end of the array, we just return the current strength.xo

The steps are as follows:-

// Recursive function to find maximum strength

     function  getMaxStrengthUtil(int index, [int] ARR, int  currStrength, int  N):

1. If index==N
   • return currStrength
2. Call the getMaxStrengthUtil function with index+1 and same currStrength and sore the result in a variable ‘maxStrength_1’
3. Call the getMaxStrengthUtil function with index+1 and currStrength as bitwise XOR of currStrength and ARR[index] and store result in a variable ‘maxStrength_2’.
4. Return the maximum of  ‘maxStrength_1’ and ‘maxStrength_2’.

function getMaxStrength( [int] ARR, int N, int K):

1. Initialise maxStrength = 0
2. Call the getMaxStrengthUtil function with index as 0, currStrength as K, A, and N
3. return maxStrength

We can use the memoization technique to store the result for each state with a particular ‘index’ and ‘currStrength.’ This way, we can save time from recalculating the already calculated results.

We can observe that in this problem,  the result of bitwise XOR among all the possible operations  will always be less than 2¹⁰  because the ‘K’ and all array elements are less than

2¹⁰ and therefore, the 10th bit and bits after the 10th bit will never be set

For memoization, let us define a 2-dimensional array DP of size (N+1) * 2¹⁰

Where DP[ i ] [ j ] denotes maximum possible strength possible with ARR[ i…N-1 ] having currStrength as  j 

The steps are as follows:-

function  getMaxStrengthUtil(int index, [int] ARR, int  currStrength, int  N, [int] [int] DP): 
 

1. if(index==N) then return currStrength
2. If DP [ index ] [ currStrength ] is not equal to -1 then return DP[ index ] [ currStrength ]
3. Now we have two options for the current element either we take it in a subset or not
   • If we do not take it, then call getMaxStrengthUtil with index+1 and the same value of currStrength and store its return value.
   • If we take the current element then we call getMaxStrengthUtil with index+1 and currentStrength as currStrength XOR ARR[ index ] and store it’s return value.
   • Now we take the maximum of above two values and assign it to DP[ index ] [ currStrength ].
4. return DP[ index ] [ currStrength ]

 

function getMaxStrength( [int] ARR , int N, int K):

1. Initialise a two-dimensional integer array ‘DP’ of size (N+1) *(2¹⁰).
2. Initialise all the elements of of ‘DP’ with -1.
3. Call the getMaxStrengthUtil function with ‘index’=0 , ‘currStrength’ = K and store the result in ‘ANS’ variable.
4. Return the ‘ANS’ variable.

The idea is the same as memoization. We are going to use recurrence relation : 

 DP [ i ] [ j ] =  max ( DP [ i+1 ] [ j ] , DP [ i +1 ] [ j XOR ARR[ i ] ) with base case DP [ i ] [ j ] = j if i == N . 
The idea behind this recurrence relation is that if we are at index ‘i’ having current strength as j then one option is to not put the current element in the subset and move forward which is DP [ i+1 ] [ j ] and the other option is to put it in the subset and move forward which is DP [ i + 1 ] [ j XOR ARR[ i ] ] and in the end, we choose best of these two options.

DP [ i ] [ j ] denotes the maximum strength possible for array ARR [ i … N-1 ] with currStrength as ‘ j ‘ .

The steps are as follows:-

function getMaxStrength ( [int] A , int N ,int K)

1. Initialise a two-dimensional integer array ‘DP’ of size (N+1) *(2¹⁰).
2. Run a loop from i=N to 0 :
   • Run a loop from j= 0 to 2¹⁰ :
     • If ( i  == N )
       1. DP [ i ] [ j ] = j .
       2. continue.
     • Use the recurrence relation :  DP [ i ] [ j ] =  max ( DP [ i+1 ] [ j ] , DP [ i +1 ] [ j XOR ARR[ i ] ).
3. return DP [ 0 ] [ K ] .