Media.Net OA | SDE1 | Fresher | July 2023 | Set - 4 | Xor Subsequences.

Question

XOR subsequences

Problem Description

 

You are given an array A, you have to create an array B which is a subsequence of A.
An array B is called valid if it satisfies both the conditions

 

1. B[i] < B[i+1] where 1 <= i<|B|.
2. bit_count( B[1] ^. ^ B[i-1] ^ B[i]) <= bit_count(B[i+1]) where 1 <= i < |B|.
   .........
   Let X be the Bitwise XOR of all the elements in valid array B.
   You need to find the number of different values of X that can be formed.
   Note: bit_count(t) is the number of set bits present in the binary representation of t

Problem Constraints

 

1 <= IAl <= 10^5
1 <= A[i] <= 100

 

Input Format

 

The first argument is an integer array A

 

Output Format

 

Return an integer denoting the number of different values of X that can be formed