Count number of common elements between two arrays

0 0 12 minutes read

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 1: 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^th position of first and second bitsets are also 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;
}

Java

/*package whatever //do not write package name here */
 
import java.util.*;
 
public class GFG {
  static int bit1 = 0;
  static int bit2 = 0;
  static int bit3 = 0;
 
  // Function to return the count of common elements
  static 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 (index)position a[i]
      bit1 = bit1 | (1 << a[i]);
    }
    // Traverse the second array
    for (int i = 0; i < m; i++) {
 
      // 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
    int count = Integer.toBinaryString(bit3).split("1").length - 1;
    return count;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[] a = { 1, 4, 7, 2, 3 };
    int[] b = { 2, 11, 7, 4, 15, 20, 24 };
    int n = a.length;
    int m = b.length;
 
    System.out.println(count_common(a, n, b, m));
  }
}
 
// This code is contributed by aadityaburujwale.

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

C#

// C# implementation of the approach
using System;
 
class GFG {
  static int bit1 = 0;
  static int bit2 = 0;
  static int bit3 = 0;
 
  // Function to return the count of common elements
  static 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 (index)position a[i]
      bit1 = bit1 | (1 << a[i]);
    }
    // Traverse the second array
    for (int i = 0; i < m; i++) {
 
      // 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
    var count
      = Convert.ToString(bit3, 2).Split("1").Length
      - 1;
    return count;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int[] a = { 1, 4, 7, 2, 3 };
    int[] b = { 2, 11, 7, 4, 15, 20, 24 };
    int n = a.Length;
    int m = b.Length;
 
    Console.WriteLine(count_common(a, n, b, m));
  }
}
 
// This code is contributed by phasing17

Javascript

// JavaScript implementation of the approach 
 
const MAX = 100000;
let bit1 = 0;
let bit2 = 0;
let bit3 = 0;
 
// Function to return the count of common elements 
function count_common(a, n, b, m) 
{
 
    // Traverse the first array 
    for (var i = 0; i < n; i++)
    {
        // Set 1 at (index)position a[i]
        bit1 = bit1 | (1<<a[i]);
    }
    // Traverse the second array 
    for (var i = 0; i < m; i++)
    {
 
        // 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 
    var count = bit3.toString(2).split("1").length - 1;
    return count; 
}
 
 
// Driver code 
var a = [ 1, 4, 7, 2, 3 ]; 
var b = [ 2, 11, 7, 4, 15, 20, 24 ]; 
var n = a.length; 
var m = b.length;
 
console.log(count_common(a, n, b, m)); 
 
// This code is contributed by phasing17

Output:

Time Complexity: O(n + m)

Auxiliary Space: O(MAX)

Approach 2: We can also use hashmap to store frequencies of each element of both arrays a[] and b[] and sum up the minimum value for each element’s frequency.

Follow given steps to solve the problem:

1. Traverse array a[] and store all frequencies in map freq1.

2. Traverse array b[] and store all frequencies in map freq2.

3. Traverse the map freq1 and sum up the minimum value between x.second and freq2[x.first] in result.

4. Return result as the final answer.

C++14

#include <bits/stdc++.h>
using namespace std;
 
int count_common(int *a, int& n, int *b, int& m)
{
    unordered_map<int,int>freq1,freq2;
    int result=0;
     
    for(int i=0;i<n;i++)
        freq1[a[i]]++;
     
    for(int i=0;i<m;i++)
        freq2[b[i]]++;
     
    for(auto& x:freq1)
        result+=min(x.second,freq2[x.first]);
     
    return result;
}
 
// driver's code
int main()
{
    int a[]={1,2,3};
    int n=sizeof(a)/sizeof(a[0]);
    int b[]={2,4,3};
    int m=sizeof(b)/sizeof(b[0]);
     
    cout<<count_common(a,n,b,m);
 
    return 0;
}
// this code is contributed by prophet1999

Java

import java.util.*;
 
public class GFG {
 
  static int count_common(int[] a, int n, int[] b, int m)
  {
    HashMap<Integer, Integer> freq1 = new HashMap<>();
    HashMap<Integer, Integer> freq2 = new HashMap<>();
 
    int result = 0;
 
    for (int i = 0; i < n; i++) {
      if (!freq1.containsKey(a[i])) {
        freq1.put(a[i], 1);
      }
      else {
        freq1.put(a[i], freq1.get(a[i]) + 1);
      }
    }
 
    for (int i = 0; i < m; i++) {
      if (!freq2.containsKey(b[i])) {
        freq2.put(b[i], 1);
      }
      else {
        freq2.put(b[i], freq2.get(b[i]) + 1);
      }
    }
 
    for (Map.Entry<Integer, Integer> x :
         freq1.entrySet()) {
      int p = x.getValue();
      int q = 0;
      if (freq2.containsKey(x.getKey())) {
        q = freq2.get(x.getKey());
      }
      result += Math.min(p, q);
    }
 
    return result;
  }
 
  // driver's code
  public static void main(String args[])
  {
    int[] a = { 1, 2, 3 };
    int n = a.length;
    int[] b = { 2, 4, 3 };
    int m = b.length;
 
    System.out.print(count_common(a, n, b, m));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python

def count_common(a, n, b, m):
 
    freq1 = {}
    freq2 = {}
    result = 0
 
    for element in a:
        if element in freq1:
            freq1[element] += 1
        else:
            freq1[element] = 1
 
    for element in b:
        if element in freq2:
            freq2[element] += 1
        else:
            freq2[element] = 1
 
    for key, value in freq1.items():
        if key in freq2:
            result += min(value, freq2.get(key))
 
    return result
 
# driver's code
a = [1, 2, 3]
n = len(a)
b = [2, 4, 3]
m = len(b)
 
print(count_common(a, n, b, m))
 
# This code is contributed by Samim Hossain Mondal.

C#

using System;
using System.Collections.Generic;
 
class GFG {
 
  static int count_common(int[] a, int n, int[] b, int m)
  {
    Dictionary<int, int> freq1
      = new Dictionary<int, int>();
 
    Dictionary<int, int> freq2
      = new Dictionary<int, int>();
 
    int result = 0;
 
    for (int i = 0; i < n; i++) {
      if (!freq1.ContainsKey(a[i])) {
        freq1.Add(a[i], 1);
      }
      else {
        freq1[a[i]]++;
      }
    }
 
    for (int i = 0; i < m; i++) {
      if (!freq2.ContainsKey(b[i])) {
        freq2.Add(b[i], 1);
      }
      else {
        freq2[b[i]]++;
      }
    }
 
    foreach(KeyValuePair<int, int> x in freq1)
    {
      int p = x.Value;
      int q = 0;
      if (freq2.ContainsKey(x.Key)) {
        q = freq2[x.Key];
      }
      result += Math.Min(p, q);
    }
 
    return result;
  }
 
  // driver's code
  public static void Main()
  {
    int[] a = { 1, 2, 3 };
    int n = a.Length;
    int[] b = { 2, 4, 3 };
    int m = b.Length;
 
    Console.Write(count_common(a, n, b, m));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

function count_common(a, n, b, m)
{
    let freq1 = new Map();
    let freq2 = new Map();
    let result = 0;
     
    for(let i = 0; i < n; i++)
        if(freq1.has(a[i]))
            freq1.set(a[i], freq1.get(a[i])+1);
        else
            freq1.set(a[i], 1);
     
    for(let i = 0; i < m; i++)
        if(freq2.has(b[i]))
            freq2.set(b[i], freq2.get(b[i])+1);
        else
            freq2.set(b[i], 1);
     
    freq1.forEach((value, key) => {
        if(freq2.has(key)){
            result += Math.min(value, freq2.get(key));
        }
        else{
            result += Math.min(value, 0);
        }
    });
         
    return result;
}
 
// driver's code
let a = [1,2,3];
let n = a.length;
let b = [2,4,3];
let m = b.length;
     
console.log(count_common(a, n, b, m));
 
// this code is contributed by Samim Hossain Mondal.

Output

Time Complexity: O(n+m)
Auxiliary Space: O(n+m)

Approach 3 : We can also use Binary search to check if the element of array a present in the array b or not.

1. Sort the array b in ascending order.
2. Initialize count as 0 , which we store the number of common elements from array a and array b.
3. Iterate each element in array a and use binary search to check if the element exists in array b.
4.If the element exists in array b, increase the count by 1.
5.Return the count .

Below is the implementation of the above approach :

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check that element x is present in the array
bool binarysearch(int arr[], int m, int x)
{
    int l = 0, r = m - 1;
 
    while (l <= r) {
        int mid = (l + r) / 2;
 
        // Checking if the middle element is equal to x
        if (arr[mid] == x) {
            return true;
        }
        else if (arr[mid] < x) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    // return true , if element x is present in the array
    // else false
    return false;
}
 
// Function to count common element
int count_common(int a[], int n, int b[], int m)
{  
    sort(b, b + m);
    int count = 0;
 
    // Iterate each element of array a
    for (int i = 0; i < n; i++) {
 
        // Checking  if the element of array a is present in
        // array b using the binary search function
        if (binarysearch(b, m, a[i])) {
            count++;
        }
    }
    // Return count of common element
    return count;
}
// Drive Code
int main()
{
    int a[] = { 1, 4, 7, 2, 3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    int b[] = { 2, 11, 7, 4, 15, 20, 24 };
    int m = sizeof(b) / sizeof(b[0]);
 
    // Function call
    cout << "Number of common elements: "
         << count_common(a, n, b, m) << "\n";
    return 0;
}
 
// This code is contributed by nikhilsainiofficial546

Java

import java.util.Arrays;
 
class GFG 
{
   
  // Function to check that element x is present in the
  // array
  public static boolean binarysearch(int arr[], int m,
                                     int x)
  {
    int l = 0;
    int r = m - 1;
 
    while (l <= r) {
      int mid = (l + r) / 2;
 
      // Checking if the middle element is equal to x
      if (arr[mid] == x) {
        return true;
      }
      else if (arr[mid] < x) {
        l = mid + 1;
      }
      else {
        r = mid - 1;
      }
    }
    // return true , if element x is present in the
    // array else false
    return false;
  }
 
  // Function to count common element
  public static int count_common(int a[], int n, int b[],
                                 int m)
  {
    Arrays.sort(b);
    int count = 0;
 
    // Iterate each element of array a
    for (int i = 0; i < n; i++) {
 
      // Checking  if the element of array a is
      // present in array b using the binary search
      // function
      if (binarysearch(b, m, a[i])) {
        count++;
      }
    }
    // Return count of common element
    return count;
  }
 
  // Drive Code
  public static void main(String[] args)
  {
    int a[] = { 1, 4, 7, 2, 3 };
    int n = a.length;
 
    int b[] = { 2, 11, 7, 4, 15, 20, 24 };
    int m = b.length;
 
    // Function call
    System.out.println("Number of common elements: "
                       + count_common(a, n, b, m));
  }
}
 
// This code is contributed by phasing17.

Python3

# python3 implementation of the above approach
 
# Function to check that element x is present in the array
def binarysearch(arr, m, x):
    l, r = 0, m - 1
     
    while l <= r:
        mid = (l + r) // 2
         
        # Checking if the middle element is equal to x
        if arr[mid] == x:
            return True
        elif arr[mid] < x:
            l = mid + 1
        else:
            r = mid - 1
             
   # return true , if element x is present in the array
   # else false
    return False
 
# Function to count common element
def count_common(a, n, b, m):
    b.sort()
    count = 0
     
    # Iterate each element of array a
    for i in range(n):
       
        # Checking  if the element of array a is present in
        # array b using the binary search function
        if binarysearch(b, m, a[i]): 
             count += 1
    # Return count of common element
    return count
 
# Drive Code
a = [1, 4, 7, 2, 3]
n = len(a)
b = [2, 11, 7, 4, 15, 20, 24]
m = len(b)
 
# Function call
print("Number of common elements:", count_common(a, n, b, m))
 
# This code is contributed by nikhilsainiofficial546

C#

// C# program to count common elements in two arrays
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
class GFG {
  static void Main(string[] args)
  {
    int[] a = new int[] { 1, 4, 7, 2, 3 };
    int n = a.Length;
 
    int[] b = new int[] { 2, 11, 7, 4, 15, 20, 24 };
    int m = b.Length;
 
    // Function call
    Console.WriteLine("Number of common elements: "
                      + count_common(a, n, b, m));
    Console.ReadLine();
  }
 
  // Function to count common element
  public static int count_common(int[] a, int n, int[] b,
                                 int m)
  {
    Array.Sort(b);
    int count = 0;
 
    // Iterate each element of array a
    for (int i = 0; i < n; i++) {
 
      // Checking  if the element of array a is
      // present in array b using the binary search
      // function
      if (binarysearch(b, m, a[i])) {
        count++;
      }
    }
    // Return count of common element
    return count;
  }
 
  // Function to check that element x is present in the
  // array
  public static bool binarysearch(int[] arr, int m, int x)
  {
    int l = 0;
    int r = m - 1;
 
    while (l <= r) {
      int mid = (l + r) / 2;
 
      // Checking if the middle element is equal to x
      if (arr[mid] == x) {
        return true;
      }
      else if (arr[mid] < x) {
        l = mid + 1;
      }
      else {
        r = mid - 1;
      }
    }
     
    // return true , if element x is present in the
    // array else false
    return false;
  }
}
 
// This code is contributed by phasing17.

Javascript

// JavaScript implementation of the above approach
 
// Function to check that element x is present in the array
function binarysearch(arr, m, x) {
let l = 0;
let r = m - 1;
while (l <= r) {
    let mid = Math.floor((l + r) / 2);
     
    // Checking if the middle element is equal to x
    if (arr[mid] === x) {
        return true;
    } else if (arr[mid] < x) {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}
// return true , if element x is present in the array
// else false
return false;
}
 
// Function to count common element
function count_common(a, n, b, m) {
a.sort(function(x, y)
{
    return x - y;
});
 
b.sort(function(x, y)
{
    return x - y;
});
let count = 0;
 
// Iterate each element of array a
for (let i = 0; i < n; i++) {
   
    // Checking  if the element of array a is present in
    // array b using the binary search function
    if (binarysearch(b, m, a[i])) { 
         count++;
    }
}
// Return count of common element
return count;
}
 
// Drive Code
let a = [1, 4, 7, 2, 3];
let n = a.length;
let b = [2, 11, 7, 4, 15, 20, 24];
let m = b.length;
 
// Function call
console.log("Number of common elements:", count_common(a, n, b, m));
 
// This code is contributed by phasing17

Output

Number of common elements: 3

Time Complexity: O(mlogm + nlogm)
Auxiliary Space: O(m)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!