# Count number of common elements between two arrays by using Bitset and Bitwise operation

Given two arrays **a[]** and **b[]**, the task is to find the count of common elements in both the given arrays. **Note** that both the arrays contain distinct (individually) positive integers.

**Examples:**

Input:a[] = {1, 2, 3}, b[] = {2, 4, 3}Output:2

2 and 3 are common to both the arrays.

Input:a[] = {1, 4, 7, 2, 3}, b[] = {2, 11, 7, 4, 15, 20, 24}Output:3

**Approach:** We will use 3 bitset of same size. First we will traverse first array and set the bit 1 to position **a[i]** in first bitset.

After that we will traverse second array and set the bit 1 to position **b[i]** in second bitset.

At last we will find the bitwise AND of both the bitsets and if the **i ^{th}** position of the resultant bitset is

**1**then it implies that

**i**position of first and second bitsets are also

^{th}**1**and

**i**is the common element in both the arrays.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `#define MAX 100000` `bitset<MAX> bit1, bit2, bit3;` ` ` `// Function to return the count of common elements` `int` `count_common(` `int` `a[], ` `int` `n, ` `int` `b[], ` `int` `m)` `{` ` ` ` ` `// Traverse the first array` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` ` ` `// Set 1 at position a[i]` ` ` `bit1.set(a[i]);` ` ` `}` ` ` ` ` `// Traverse the second array` ` ` `for` `(` `int` `i = 0; i < m; i++) {` ` ` ` ` `// Set 1 at position b[i]` ` ` `bit2.set(b[i]);` ` ` `}` ` ` ` ` `// Bitwise AND of both the bitsets` ` ` `bit3 = bit1 & bit2;` ` ` ` ` `// Find the count of 1's` ` ` `int` `count = bit3.count();` ` ` ` ` `return` `count;` `}` ` ` `// Driver code` `int` `main()` `{` ` ` ` ` `int` `a[] = { 1, 4, 7, 2, 3 };` ` ` `int` `b[] = { 2, 11, 7, 4, 15, 20, 24 };` ` ` `int` `n = ` `sizeof` `(a) / ` `sizeof` `(a[0]);` ` ` `int` `m = ` `sizeof` `(b) / ` `sizeof` `(b[0]);` ` ` ` ` `cout << count_common(a, n, b, m);` ` ` ` ` `return` `0;` `}` |

## Python3

`# Python3 implementation of the approach ` ` ` `MAX` `=` `100000` `bit1 , bit2, bit3 ` `=` `0` `, ` `0` `, ` `0` ` ` `# Function to return the count of common elements ` `def` `count_common(a, n, b, m) : ` ` ` ` ` `# Traverse the first array ` ` ` `for` `i ` `in` `range` `(n) :` ` ` ` ` `global` `bit1, bit2, bit3` ` ` ` ` `# Set 1 at (index)position a[i]` ` ` `bit1 ` `=` `bit1 | (` `1` `<<a[i])` ` ` ` ` `# Traverse the second array ` ` ` `for` `i ` `in` `range` `(m) :` ` ` ` ` `# Set 1 at (index)position b[i] ` ` ` `bit2 ` `=` `bit2 | (` `1` `<<b[i])` ` ` ` ` `# Bitwise AND of both the bitsets ` ` ` `bit3 ` `=` `bit1 & bit2; ` ` ` ` ` `# Find the count of 1's ` ` ` `count ` `=` `bin` `(bit3).count(` `'1'` `); ` ` ` ` ` `return` `count; ` ` ` `# Driver code ` `if` `__name__ ` `=` `=` `"__main__"` `: ` ` ` ` ` `a ` `=` `[ ` `1` `, ` `4` `, ` `7` `, ` `2` `, ` `3` `]; ` ` ` `b ` `=` `[ ` `2` `, ` `11` `, ` `7` `, ` `4` `, ` `15` `, ` `20` `, ` `24` `]; ` ` ` `n ` `=` `len` `(a); ` ` ` `m ` `=` `len` `(b); ` ` ` ` ` `print` `(count_common(a, n, b, m)); ` ` ` `# This code is contributed by AnkitRai01` |

**Output:**

3

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.