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>
Producción:
2
Complejidad de tiempo: O(log(max(diff1, diff2)))