XOR DARE

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
0 upvote

Problem statement

Ninja and his friends are playing a truth or dare game. Ninja has chosen dare, and his friends have given him a problem to solve. Now ninja is unable to solve the problem, so he asks for your help.

In the problem, you are given an integer array ‘ARR’ consisting of ‘N’ elements and an integer number ‘K’.

You need to find the maximum possible strength among all the subsets of array ‘ARR’.

The strength of a set of elements is bitwise XOR of all the elements present in the set and ‘K’.

Note: For an empty subset, You can consider the XOR of its elements as 0.

Example: 
Input: ‘N’ = 3  ‘ARR’ = [1, 2, 3]  ‘K’ = 4

Output: 7

The subset [3] has the maximum possible value, which is equal to 3 XOR 4 = 7
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains ‘T’,  denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’.

The second line of each test case contains ‘N’ space-separated integers denoting the          array ‘ARR’.
Output Format : 
Return the maximum possible strength possible among all the subsets of array ‘ARR’.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= N <= 1000
0 <= ARR[i] <=1000 for ‘i’ in range 0 to N-1
0 <= K <= 1000

Time Limit: 1 sec
Sample Input 1 :
2
4 3
5 4 1 2
3 8
1 2 8
Sample Output 1 :
7
11
Explanation of sample input 1 :
For the first test case:
The subset [3] will produce maximum strength of ( 3 XOR  4 ) = 7

For the second test case:
The subset  [ 1, 2 ] will produce maximum strength of ( 1 XOR 2 XOR 8 ) = 11
Sample Input 2 :
2
2
4 3
3 3 3 3
3 7
1 2 8
Sample Output 2:
3
15
Hint

Try all the possible subsets

Approaches (3)
Recursion

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
Time Complexity

O(  2N  ), Where ‘N’ is the number of elements in integer array 'ARR'.

 

Each element has two choices. A total of N elements are in the array, so a total of 2N  possibilities is there.

 

Hence The Time complexity is O( 2N  ).

Space Complexity

O ( N ), Where ‘N’ is the number of elements in integer array ‘ARR’.

 

Extra auxiliary space will be needed for the recursion call stack.

 

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
XOR DARE
Full screen
Console