Dadas dos arrays arr1[] y arr2[] de tamaño M y N respectivamente. Ambos arreglos están en progresión aritmética y el primer elemento de ambos arreglos es el mismo. La tarea es encontrar el número de elementos comunes en arr1[] y arr2[].
Ejemplos:
Entrada: arr1[] = {2, 3, 4, 5, 6}, arr2[] = {2, 4, 6, 8, 10}
Salida: 3
Explicación:
Los elementos comunes son {2, 4, 6}
Entrada: arr1[] = {1, 4, 7, 10, 13, 16}, arr2[] = {1, 3, 5, 7, 9}
Salida: 2
Explicación:
Los elementos comunes son {1, 7}
Recomendado: pruebe su enfoque en {IDE} primero, antes de pasar a la solución.
Enfoque: La idea es usar el mínimo común múltiplo de la diferencia común de las dos progresiones aritméticas para resolver este problema. A continuación se muestra la ilustración de los pasos:
- Encuentre la diferencia común de las dos progresiones aritméticas con la ayuda de las siguientes fórmulas
diff1 = arr1[1] - arr1[0] diff2 = arr2[1] - arr2[0]
- Encuentra el mínimo común múltiplo de la diferencia común de las dos progresiones aritméticas.
- Los elementos comunes posibles en las dos progresiones aritméticas serán la diferencia de los últimos elementos de la progresión aritmética al primer elemento dividida por el MCM de la diferencia común.
elements1 = (arr1[m-1] - arr1[0]) / LCM(diff1, diff2) elements2 = (arr2[n-1] - arr2[0]) / LCM(diff1, diff2) // Common Elements ans = min(elements, elements2)
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(log(max(diff1, diff2)))