Saturday, 23 Oct 2021

# Count subsequences having odd Bitwise XOR values from an array

Given an array A[] of size N, the task is to count the number of subsequences from the given array whose Bitwise XOR value is odd.
Examples:

Input: A[] = { 1, 3, 4 }Output: 4Explanation: Subsequences with odd Bitwise XOR are { 1 }, { 3} , { 1, 4 }, { 3, 4 }.
Input: A[] = { 2, 8, 6 }Output: 0Explanation: No such subsequences are present in the array.

Naive Approach: The simplest approach to solve the problem is to generate all the subsequences of the given array and for each subsequence, check if its Bitwise XOR value is odd or not. If found to be odd, then increase the count by one. After checking for all subsequences, print the count obtained.Time Complexity: O(N * 2N)Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the observation that a subsequence will have odd Bitwise XOR only if the number of odd elements present in it is odd. This is because odd elements have the least significant bit equal to 1. Therefore, XOR of the least significant bits (1^1^1….) up to an odd number of times sets the least significant bit of the new number formed. Therefore, the new number formed is odd.Follow the steps below to solve the problem:
Store the count of even and odd elements present in the array A[] in even and odd respectively.
Traverse the array A[] using the variable i
If the value of A[i] is odd, increase the value of odd by 1.
Otherwise, increase the value of even by 1.

If the value of odd is equal to 0, then print 0 and return.
Otherwise,
Find the total combinations with an odd number of odd elements.
This can be caluclated by (XC1+XC3+…+XC(x-(x+1)%2)) * (MC0+MC1+…+MCM) = 2X-1 * 2M = 2X+M-1= 2N-1.
Therefore, Print 2N-1

Below is the implementation of the above approach:

Java

import java.io.*;

class GFG {

public static void countSubsequences(int[] A)
{

int odd = 0;

int even = 0;

for (int el : A) {

if (el % 2 == 1)
odd++;
else
even++;
}

if (odd == 0)
System.out.println(0);

else
System.out.println(1