Count common elements in two arrays which are in Arithmetic Progression
Given two arrays arr1[] and arr2[] of size M and N respectively. Both arrays are in Arithmetic Progression and the first element of both arrays is the same. The task is to find the number of common elements in arr1[] and arr2[].
Examples:
Input: arr1[] = {2, 3, 4, 5, 6}, arr2[] = {2, 4, 6, 8, 10}
Output: 3
Explanation:
Common elements are {2, 4, 6}
Input: arr1[] = {1, 4, 7, 10, 13, 16}, arr2[] = {1, 3, 5, 7, 9}
Output: 2
Explanation:
Common elements are {1, 7}
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: The idea is to use Least Common Multiple of the common difference of the two Arithmetic Progression to solve this problem. Below is the illustration of the steps:
- Find the common difference of the two arithmetic progression with the help of the below formulae
diff1 = arr1[1] - arr1[0] diff2 = arr2[1] - arr2[0]
- Find the Least common multiple of the common difference of the two arithmetic progression.
- Common elements that are possible in the two arithmetic progression will be the difference of the last elements of the arithmetic progression to the first element divided by the LCM of the common difference.
elements1 = (arr1[m-1] - arr1[0]) / LCM(diff1, diff2) elements2 = (arr2[n-1] - arr2[0]) / LCM(diff1, diff2) // Common Elements ans = min(elements, elements2)
Below is the implementation of the above approach:
C++
// C++ implementation to count the // common elements of the two arithmetic // progression of the given sequence #include<bits/stdc++.h> using namespace std; // Function to find GCD int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find LCM int findlcm( int a, int b) { int gc = gcd(a, b); return a * b / gc; } // Function to count common element // of arr1[] and arr2[] int CountCommon( int arr1[], int arr2[], int m, int n) { // Common Difference int diff1 = arr1[1] - arr1[0]; int diff2 = arr2[1] - arr2[0]; // Function calling int lcm = findlcm(diff1, diff2); int ans1 = (arr1[m - 1] - arr1[0]) / lcm; int ans2 = (arr2[n - 1] - arr2[0]) / lcm; int ans = min(ans1, ans2); return (ans + 1); } // Driver code int main() { int arr1[] = { 2, 5, 8, 11, 14, 17 }; int arr2[] = { 2, 4, 6, 8, 10, 12 }; int m = sizeof (arr1) / sizeof (arr1[0]); int n = sizeof (arr2) / sizeof (arr2[0]); // Function calling cout << CountCommon(arr1, arr2, m, n); return 0; } // This code is contributed by amal kumar choubey |
Java
// Java implementation to count the // common elements of the two arithmetic // progression of the given sequence import java.util.*; class GFG{ // Function to find GCD static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to find LCM static int findlcm( int a, int b) { int gc = gcd(a, b); return a * b / gc; } // Function to count common element // of arr1[] and arr2[] static int CountCommon( int []arr1, int []arr2, int m, int n) { // Common Difference int diff1 = arr1[ 1 ] - arr1[ 0 ]; int diff2 = arr2[ 1 ] - arr2[ 0 ]; // Function calling int lcm = findlcm(diff1, diff2); int ans1 = (arr1[m - 1 ] - arr1[ 0 ]) / lcm; int ans2 = (arr2[n - 1 ] - arr2[ 0 ]) / lcm; int ans = Math.min(ans1, ans2); return (ans + 1 ); } // Driver code public static void main(String args[]) { int []arr1 = { 2 , 5 , 8 , 11 , 14 , 17 }; int []arr2 = { 2 , 4 , 6 , 8 , 10 , 12 }; int m = arr1.length; int n = arr2.length; // Function calling System.out.print(CountCommon(arr1, arr2, m, n)); } } // This code is contributed by Nidhi_biet |
Python3
# Python3 implementation to count the # common elements of the two arithmetic # progression of the given sequence # Function to find GCD def gcd(a, b): if b = = 0 : return a return gcd(b, a % b) # Function to find LCM def findlcm(a, b): return a * b / / gcd(a, b) # Function to count Common Element # of arr1[] and arr2[] def CountCommon(arr1, arr2, m, n): # Common Difference diff1 = arr1[ 1 ] - arr1[ 0 ] diff2 = arr2[ 1 ] - arr2[ 0 ] # Function calling lcm = findlcm(diff1, diff2) ans1 = (arr1[m - 1 ] - arr1[ 0 ]) / / lcm ans2 = (arr2[n - 1 ] - arr2[ 0 ]) / / lcm ans = min (ans1, ans2) # Print the total Common Element print (ans + 1 ) # Driver Code if __name__ = = "__main__" : arr1 = [ 2 , 5 , 8 , 11 , 14 , 17 ] arr2 = [ 2 , 4 , 6 , 8 , 10 , 12 ] m = len (arr1) n = len (arr2) # Function calling CountCommon(arr1, arr2, m, n) |
C#
// C# implementation to count the // common elements of the two arithmetic // progression of the given sequence using System; class GFG{ // Function to find GCD static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find LCM static int findlcm( int a, int b) { int gc = gcd(a, b); return a * b / gc; } // Function to count common element // of arr1[] and arr2[] int CountCommon( int []arr1, int []arr2, int m, int n) { // Common Difference int diff1 = arr1[1] - arr1[0]; int diff2 = arr2[1] - arr2[0]; // Function calling int lcm = findlcm(diff1, diff2); int ans1 = (arr1[m - 1] - arr1[0]) / lcm; int ans2 = (arr2[n - 1] - arr2[0]) / lcm; int ans = min(ans1, ans2); return (ans + 1); } // Driver code public static void Main() { int []arr1 = { 2, 5, 8, 11, 14, 17 }; int []arr2 = { 2, 4, 6, 8, 10, 12 }; int m = arr1.Length; int n = arr2.Length; // Function calling Console.Write(CountCommon(arr1, arr2, m, n)); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript implementation to count the // common elements of the two arithmetic // progression of the given sequence // Function to find GCD function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find LCM function findlcm(a, b) { let gc = gcd(a, b); return a * b / gc; } // Function to count common element // of arr1[] and arr2[] function CountCommon(arr1, arr2, m, n) { // Common Difference let diff1 = arr1[1] - arr1[0]; let diff2 = arr2[1] - arr2[0]; // Function calling let lcm = findlcm(diff1, diff2); let ans1 = Math.floor((arr1[m - 1] - arr1[0]) / lcm); let ans2 = Math.floor((arr2[n - 1] - arr2[0]) / lcm); let ans = Math.min(ans1, ans2); return (ans + 1); } // Driver code let arr1 = [ 2, 5, 8, 11, 14, 17 ]; let arr2 = [ 2, 4, 6, 8, 10, 12 ]; let m = arr1.length; let n = arr2.length; // Function calling document.write(CountCommon(arr1, arr2, m, n)); // This code is contributed by Mayank Tyagi </script> |
2
Time Complexity:O(log(max(diff1, diff2)))
Auxiliary Space: O(log(max(diff1, diff2)))
Another Approach: We can Binary search to check if the element of first array is present in the second array or not because first and second array is already sorted in increasing order. So , we will use binary search for finding common elements.
Below is the implementation of the above approach :
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; //Function to check if x is present in the array or not 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 the number of // elements common in both the arrays int CountCommon( int A[], int B[], int N, int 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 if (binarysearch(B, M, A[i])) { count++; } } //return count of common elements return count; } // Driver Code int main() { int A[] = { 2, 5, 8, 11, 14, 17 }; int B[] = {2, 4, 6, 8, 10, 12}; int N = sizeof (A) / sizeof ( int ); int M = sizeof (B) / sizeof ( int ); //Function call cout<< CountCommon(A, B, N, M)<< "\n" ; return 0; } // This code is contributed by nikhilsainiofficial546 |
Java
// Java program for the above approach import java.util.*; public class Main { // Function to check if x is present in the array or // not public static boolean 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 the number of // elements common in both the arrays public static int CountCommon( int A[], int B[], int N, int 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 if (binarysearch(B, M, A[i])) { count++; } } // return count of common elements return count; } // Driver Code public static void main(String[] args) { int A[] = { 2 , 5 , 8 , 11 , 14 , 17 }; int B[] = { 2 , 4 , 6 , 8 , 10 , 12 }; int N = A.length; int M = B.length; // Function call System.out.println(CountCommon(A, B, N, M)); } } |
Python3
from typing import List # Function to check if x is present in the array or not def binarysearch(arr: List [ int ], M: int , x: int ) - > bool : 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 the number of elements common in both the arrays def count_common(A: List [ int ], B: List [ int ], N: int , M: int ) - > int : 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 binary search if binarysearch(B, M, A[i]): count + = 1 # return count of common elements return count # Driver Code if __name__ = = '__main__' : A = [ 2 , 5 , 8 , 11 , 14 , 17 ] B = [ 2 , 4 , 6 , 8 , 10 , 12 ] N = len (A) M = len (B) # Function call print (count_common(A, B, N, M)) |
C#
// Here is the code in C# for the above approach using System; namespace CountCommonElements { class Program { // Function to check if x is present in the array or not static 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 the number of elements common in // both the arrays static int CountCommon( int [] A, int [] B, int N, int 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 if (BinarySearch(B, M, A[i])) { count++; } } // Return count of common elements return count; } // Driver Code static void Main( string [] args) { int [] A = { 2, 5, 8, 11, 14, 17 }; int [] B = { 2, 4, 6, 8, 10, 12 }; int N = A.Length; int M = B.Length; // Function call Console.WriteLine(CountCommon(A, B, N, M)); } } } // This code is contributed by sarojmcy2e |
Javascript
// JavaScript program for the above approach // Function to check if x is present in the array or not function binarysearch(arr, M, x) { let l = 0, 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 the number of // elements common in both the arrays function CountCommon(A, B, N, M) { 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 if (binarysearch(B, M, A[i])) { count++; } } //return count of common elements return count; } // Driver Code let A = [2, 5, 8, 11, 14, 17]; let B = [2, 4, 6, 8, 10, 12]; let N = A.length; let M = B.length; //Function call console.log(CountCommon(A, B, N, M)); |
2
Time Complexity:O(N*logM)
Auxiliary Space: O(1)
Another approach using sets –
In this approach we will use the set data structure to find the common elements between those two lists. Firstly we will convert those two lists into sets and then find the intersection between them and then count the number of elements returned by that intersection and print it.
C++
#include <iostream> #include <vector> #include <unordered_set> using namespace std; int count_common_ele(vector< int > arr1, vector< int > arr2) { unordered_set< int > set_arr1(arr1.begin(), arr1.end()); unordered_set< int > set_arr2(arr2.begin(), arr2.end()); // using the intersection operator & int count1 = 0; for ( auto num : set_arr1) { if (set_arr2.count(num)) { count1++; } } cout << count1 << endl; // prints the count using & return 0; } int main() { vector< int > arr1 = {2, 5, 8, 11, 14, 17}; vector< int > arr2 = {2, 4, 6, 8, 10, 12}; count_common_ele(arr1, arr2); return 0; } // This code is contributed by divyansh2212 |
Java
import java.util.HashSet; import java.util.Set; public class Main { public static int countCommonElements( int [] arr1, int [] arr2) { Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); // populate sets from arrays for ( int num : arr1) { set1.add(num); } for ( int num : arr2) { set2.add(num); } // count common elements using the intersection // operator & int count = 0 ; for ( int num : set1) { if (set2.contains(num)) { count++; } } System.out.println( count); // prints the count using & operator return 0 ; } public static void main(String[] args) { int [] arr1 = { 2 , 5 , 8 , 11 , 14 , 17 }; int [] arr2 = { 2 , 4 , 6 , 8 , 10 , 12 }; countCommonElements(arr1, arr2); } } // This code is contributed by Prajwal Kandekar |
Python3
# Function to find count_common_elements # in two lists using set. def count_common_ele(arr1, arr2): # convering the lists # into sets set_arr1 = set (arr1) set_arr2 = set (arr2) # using the intersection() # method here print ( len (set_arr1.intersection(set_arr2))) # driving code arr1 = [ 2 , 5 , 8 , 11 , 14 , 17 ] arr2 = [ 2 , 4 , 6 , 8 , 10 , 12 ] # calling the Function count_common_ele(arr1, arr2) # This code is contributed by - Dwaipayan Bandyopadhyay |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to count the number of common elements // between two lists static int CountCommonElements(List< int > arr1, List< int > arr2) { // Convert the two lists to hash sets to efficiently // find the common elements HashSet< int > setArr1 = new HashSet< int >(arr1); HashSet< int > setArr2 = new HashSet< int >(arr2); // Using the intersection operator & to find the // common elements int count = setArr1.Intersect(setArr2).Count(); // Print the count of common elements Console.WriteLine( count); // prints the count using & // Return a dummy value since the function signature // specifies that it returns an integer return 0; } static void Main( string [] args) { // Define the two input lists List< int > arr1 = new List< int >{ 2, 5, 8, 11, 14, 17 }; List< int > arr2 = new List< int >{ 2, 4, 6, 8, 10, 12 }; // Call the CountCommonElements function and pass in // the two input lists CountCommonElements(arr1, arr2); // Wait for user input before exiting the program Console.ReadLine(); } } // This code is contributed by sarojmcy2e |
Javascript
function countCommonElements(arr1, arr2) { // converting the arrays into sets const setArr1 = new Set(arr1); const setArr2 = new Set(arr2); // using the size property of the intersection of sets console.log([...setArr1].filter(x => setArr2.has(x)).length); } // driver code const arr1 = [2, 5, 8, 11, 14, 17]; const arr2 = [2, 4, 6, 8, 10, 12]; // calling the function countCommonElements(arr1, arr2); |
2
Time Complexity – O(N + M) # Where N and M are the sizes of the arrays
Space Complexity – O(N) # converted the list into sets, N denotes the length of the list
Contact Us