# Count of even and odd set bit with array element after XOR with K

Given an array **arr[]** and a number **K**. The task is to find the count of the element having odd and even number of the set-bit after taking XOR of **K** with every element of the given **arr[]**.**Examples:**

Input:arr[] = {4, 2, 15, 9, 8, 8}, K = 3Output:Even = 2, Odd = 4Explanation:

The binary representation of the element after taking XOR with K are:

4 ^ 3 = 7 (111)

2 ^ 3 = 1 (1)

15 ^ 3 = 12 (1100)

9 ^ 3 = 10 (1010)

8 ^ 3 = 11 (1011)

8 ^ 3 = 11 (1011)

No of elements with even no of 1’s in binary representation : 2 (12, 10)

No of elements with odd no of 1’s in binary representation : 4 (7, 1, 11, 11)Input:arr[] = {4, 2, 15, 9, 8, 8}, K = 6Output:Even = 4, Odd = 2

**Naive Approach:** The naive approach is to take bitwise XOR of **K** with each element of the given array **arr[]** and then, count the set-bit for each element in the array after taking XOR with **K**.**Time Complexity:** O(N*K)**Efficient Approach:**

With the help of the following observation, we have:

For Example:

If A = 4 and K = 3

Binary Representation:

A = 100

K = 011

A^K = 111

Therefore, the XOR of numberA(which has an odd number of set-bit) with the numberK(which has an even number of set-bit) results in an odd number of set-bit.

And If A = 4 and K = 7

Binary Representation:

A = 100

K = 111

A^K = 011

Therefore, the XOR of numberA(which has an odd number of set-bit) with the numberK(which has an odd number of set-bit) results in an even number of set-bit.

From the above observations:

- If
**K**has an odd number of set-bit, then the count of elements of array**arr[]**with even set-bit and odd set-bit after taking XOR with**K**, will be same as the count of even set-bit and odd set-bit int the array before XOR. - If
**K**has an even number of set-bit, then the count of elements of array**arr[]**with even set-bit and odd set-bit after taking XOR with**K**, will reverse as the count of even set-bit and odd set-bit in the array before XOR.

**Steps**:

- Store the count of elements having even set-bit and odd set-bit from the given array
**arr[]**. - If
**K**has odd set-bit, then the count of even and odd set-bit after XOR with K will be the same as the count of even and odd set-bit calculated above. - If
**K**has even set-bit, then the count of even and odd set-bit after XOR with K will be the count of odd and even set-bit calculated above.

Below is the implementation of the above approach:

## C++

`// C++ program to count the set` `// bits after taking XOR with a` `// number K` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to store EVEN and odd variable` `void` `countEvenOdd(` `int` `arr[], ` `int` `n, ` `int` `K)` `{` ` ` `int` `even = 0, odd = 0;` ` ` `// Store the count of even and` ` ` `// odd set bit` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `// Count the set bit using` ` ` `// in built function` ` ` `int` `x = __builtin_popcount(arr[i]);` ` ` `if` `(x % 2 == 0)` ` ` `even++;` ` ` `else` ` ` `odd++;` ` ` `}` ` ` `int` `y;` ` ` `// Count of set-bit of K` ` ` `y = __builtin_popcount(K);` ` ` `// If y is odd then, count of` ` ` `// even and odd set bit will` ` ` `// be interchanged` ` ` `if` `(y & 1) {` ` ` `cout << ` `"Even = "` `<< odd` ` ` `<< ` `", Odd = "` `<< even;` ` ` `}` ` ` `// Else it will remain same as` ` ` `// the original array` ` ` `else` `{` ` ` `cout << ` `"Even = "` `<< even` ` ` `<< ` `", Odd = "` `<< odd;` ` ` `}` `}` `// Driver's Code` `int` `main(` `void` `)` `{` ` ` `int` `arr[] = { 4, 2, 15, 9, 8, 8 };` ` ` `int` `K = 3;` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `// Function call to count even` ` ` `// and odd` ` ` `countEvenOdd(arr, n, K);` ` ` `return` `0;` `}` |

## Java

`// Java program to count the set` `// bits after taking XOR with a` `// number K` `class` `GFG {` ` ` ` ` `/* Function to get no of set ` ` ` `bits in binary representation ` ` ` `of positive integer n */` ` ` `static` `int` `__builtin_popcount(` `int` `n)` ` ` `{` ` ` `int` `count = ` `0` `;` ` ` `while` `(n > ` `0` `) {` ` ` `count += n & ` `1` `;` ` ` `n >>= ` `1` `;` ` ` `}` ` ` `return` `count;` ` ` `}` ` ` ` ` `// Function to store EVEN and odd variable` ` ` `static` `void` `countEvenOdd(` `int` `arr[], ` `int` `n, ` `int` `K)` ` ` `{` ` ` `int` `even = ` `0` `, odd = ` `0` `;` ` ` ` ` `// Store the count of even and` ` ` `// odd set bit` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` ` ` `// Count the set bit using` ` ` `// in built function` ` ` `int` `x = __builtin_popcount(arr[i]);` ` ` `if` `(x % ` `2` `== ` `0` `)` ` ` `even++;` ` ` `else` ` ` `odd++;` ` ` `}` ` ` ` ` `int` `y;` ` ` ` ` `// Count of set-bit of K` ` ` `y = __builtin_popcount(K);` ` ` ` ` `// If y is odd then, count of` ` ` `// even and odd set bit will` ` ` `// be interchanged` ` ` `if` `((y & ` `1` `) != ` `0` `) {` ` ` `System.out.println(` `"Even = "` `+ odd + ` `", Odd = "` `+ even);` ` ` `}` ` ` ` ` `// Else it will remain same as` ` ` `// the original array` ` ` `else` `{` ` ` `System.out.println(` `"Even = "` `+ even + ` `", Odd = "` `+ odd);` ` ` `}` ` ` `}` ` ` ` ` `// Driver's Code` ` ` `public` `static` `void` `main (String[] args)` ` ` `{` ` ` `int` `arr[] = { ` `4` `, ` `2` `, ` `15` `, ` `9` `, ` `8` `, ` `8` `};` ` ` `int` `K = ` `3` `;` ` ` `int` `n = arr.length;` ` ` ` ` `// Function call to count even` ` ` `// and odd` ` ` `countEvenOdd(arr, n, K);` ` ` `}` ` ` `}` `// This code is contributed by Yash_R` |

## Python3

`# Python3 program to count the set` `# bits after taking XOR with a` `# number K` `# Function to store EVEN and odd variable` `def` `countEvenOdd(arr, n, K) :` ` ` `even ` `=` `0` `; odd ` `=` `0` `;` ` ` `# Store the count of even and` ` ` `# odd set bit` ` ` `for` `i ` `in` `range` `(n) :` ` ` `# Count the set bit using` ` ` `# in built function` ` ` `x ` `=` `bin` `(arr[i]).count(` `'1'` `);` ` ` `if` `(x ` `%` `2` `=` `=` `0` `) :` ` ` `even ` `+` `=` `1` `;` ` ` `else` `:` ` ` `odd ` `+` `=` `1` `;` ` ` `# Count of set-bit of K` ` ` `y ` `=` `bin` `(K).count(` `'1'` `);` ` ` `# If y is odd then, count of` ` ` `# even and odd set bit will` ` ` `# be interchanged` ` ` `if` `(y & ` `1` `) :` ` ` `print` `(` `"Even ="` `,odd ,` `", Odd ="` `, even);` ` ` `# Else it will remain same as` ` ` `# the original array` ` ` `else` `:` ` ` `print` `(` `"Even ="` `, even ,` `", Odd ="` `, odd);` `# Driver's Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` ` ` `arr ` `=` `[ ` `4` `, ` `2` `, ` `15` `, ` `9` `, ` `8` `, ` `8` `];` ` ` `K ` `=` `3` `;` ` ` `n ` `=` `len` `(arr);` ` ` `# Function call to count even` ` ` `# and odd` ` ` `countEvenOdd(arr, n, K);` ` ` `# This code is contributed by Yash_R` |

## C#

`// C# program to count the set` `// bits after taking XOR with a` `// number K` `using` `System;` `public` `class` `GFG {` ` ` ` ` `/* Function to get no of set ` ` ` `bits in binary representation ` ` ` `of positive integer n */` ` ` `static` `int` `__builtin_popcount(` `int` `n)` ` ` `{` ` ` `int` `count = 0;` ` ` `while` `(n > 0) {` ` ` `count += n & 1;` ` ` `n >>= 1;` ` ` `}` ` ` `return` `count;` ` ` `}` ` ` ` ` `// Function to store EVEN and odd variable` ` ` `static` `void` `countEvenOdd(` `int` `[]arr, ` `int` `n, ` `int` `K)` ` ` `{` ` ` `int` `even = 0, odd = 0;` ` ` ` ` `// Store the count of even and` ` ` `// odd set bit` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` ` ` `// Count the set bit using` ` ` `// in built function` ` ` `int` `x = __builtin_popcount(arr[i]);` ` ` `if` `(x % 2 == 0)` ` ` `even++;` ` ` `else` ` ` `odd++;` ` ` `}` ` ` ` ` `int` `y;` ` ` ` ` `// Count of set-bit of K` ` ` `y = __builtin_popcount(K);` ` ` ` ` `// If y is odd then, count of` ` ` `// even and odd set bit will` ` ` `// be interchanged` ` ` `if` `((y & 1) != 0) {` ` ` `Console.WriteLine(` `"Even = "` `+ odd + ` `", Odd = "` `+ even);` ` ` `}` ` ` ` ` `// Else it will remain same as` ` ` `// the original array` ` ` `else` `{` ` ` `Console.WriteLine(` `"Even = "` `+ even + ` `", Odd = "` `+ odd);` ` ` `}` ` ` `}` ` ` ` ` `// Driver's Code` ` ` `public` `static` `void` `Main (` `string` `[] args)` ` ` `{` ` ` `int` `[]arr = { 4, 2, 15, 9, 8, 8 };` ` ` `int` `K = 3;` ` ` `int` `n = arr.Length;` ` ` ` ` `// Function call to count even` ` ` `// and odd` ` ` `countEvenOdd(arr, n, K);` ` ` `}` ` ` `}` `// This code is contributed by Yash_R` |

## Javascript

`<script>` `// Javascript program to count the set` `// bits after taking XOR with a` `// number K` `/* Function to get no of set` `bits in binary representation` `of positive integer n */` `function` `__builtin_popcount(n) {` ` ` `let count = 0;` ` ` `while` `(n > 0) {` ` ` `count += n & 1;` ` ` `n >>= 1;` ` ` `}` ` ` `return` `count;` `}` `// Function to store EVEN and odd variable` `function` `countEvenOdd(arr, n, K) {` ` ` `let even = 0, odd = 0;` ` ` `// Store the count of even and` ` ` `// odd set bit` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `// Count the set bit using` ` ` `// in built function` ` ` `let x = __builtin_popcount(arr[i]);` ` ` `if` `(x % 2 == 0)` ` ` `even++;` ` ` `else` ` ` `odd++;` ` ` `}` ` ` `let y;` ` ` `// Count of set-bit of K` ` ` `y = __builtin_popcount(K);` ` ` `// If y is odd then, count of` ` ` `// even and odd set bit will` ` ` `// be interchanged` ` ` `if` `((y & 1) != 0) {` ` ` `document.write(` `"Even = "` `+ odd + ` `", Odd = "` `+ even);` ` ` `}` ` ` `// Else it will remain same as` ` ` `// the original array` ` ` `else` `{` ` ` `document.write(` `"Even = "` `+ even + ` `", Odd = "` `+ odd);` ` ` `}` `}` `// Driver's Code` `let arr = [4, 2, 15, 9, 8, 8];` `let K = 3;` `let n = arr.length;` `// Function call to count even` `// and odd` `countEvenOdd(arr, n, K);` `// This code is contributed by _saurabh_jaiswal` `</script>` |

**Output:**

Even = 2, Odd = 4

**Time Complexity:** O(N)