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 ith position of the resultant bitset is 1 then it implies that ith 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 100000bitset<MAX> bit1, bit2, bit3;// Function to return the count of common elementsint 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 codeint 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 = 100000bit1 , 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 approachusing 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:
3
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 codeint 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 codea = [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 codelet 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
2
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 arraybool 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 elementint 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 Codeint 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 arraydef 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 elementdef 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 Codea = [1, 4, 7, 2, 3]n = len(a)b = [2, 11, 7, 4, 15, 20, 24]m = len(b)# Function callprint("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 arraysusing 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 arrayfunction 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 falsereturn false;}// Function to count common elementfunction 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 afor (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 elementreturn count;}// Drive Codelet a = [1, 4, 7, 2, 3];let n = a.length;let b = [2, 11, 7, 4, 15, 20, 24];let m = b.length;// Function callconsole.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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
