[Solved] Append for OR STARTERS 73 CodeChef

Chef has an array AA of length NN.

Chef wants to append a non-negative integer XX to the array AA such that the bitwise OR of the entire array becomes = Y=Y i.e. (A_1 \ | \ A_2 \ | \ \ldots \ | \ A_N \ | \ X) = Y(A1​ ∣ A2​ ∣ … ∣ AN​ ∣ X)=Y. (Here, |∣ denotes the bitwise OR operation)

Determine the minimum possible value of XX. If no possible value of XX exists, output -1−1.

Input Format

• The first line contains a single integer TT — the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers NN and YY — the size of the array AA and final bitwise OR of the array AA.
• The second line of each test case contains NN space-separated integers A_1, A_2, \dots, A_NA1​,A2​,…,AN​ denoting the array AA.

Output Format

For each test case, output the minimum possible value of XX for which (A_1 \ | \ A_2 \ | \ \ldots \ | \ A_N \ | \ X) = Y(A1​ ∣ A2​ ∣ … ∣ AN​ ∣ X)=Y holds.

If no such value exists, output -1−1.

Constraints

• 1≤T≤10^5
• 1≤N≤10^5
• 0≤Ai​<2^20
• 0≤Y<2^20
• Sum of NN over all test cases does not exceed 2.10^5

Sample 1:

Input:

4
4 15
3 5 6 2
3 8
1 2 1
1 1
0
5 7
1 2 4 2 1

Output:

8
-1
1
0

Explanation:

Test Case 1: (3 ∣ 5 ∣ 6 ∣ 2 ∣ X)=15 holds for the following values of XX: {8,9,10,11,12,13,14,15}. The minimum among them is 88.

Test Case 2: It can be proven that no valid value of XX exists.

Test Case 3: (0 ∣ X)=1 holds for only X = 1X=1.

Solution

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		 Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int y = sc.nextInt();
            int[] a = new int[n];
            int or = 0;
            for(int i=0;i<n;i++){
                a[i] = sc.nextInt();
                or = or | a[i];
            }
            if(or == y){
                System.out.println(0);
            }else{
                int x = or ^ y;
                if((x | or) == y){
                    System.out.println(x);
                }else{
                    System.out.println(-1);
                }
            }
        }
	}
}

Happy Learning – If you require any further information, feel free to contact me.