Dadas dos arrays de enteros A[] y D[] , donde A i y D i representan el primer elemento y la diferencia común de una progresión aritmética respectivamente, la tarea es encontrar un elemento que sea común en el número máximo de progresiones aritméticas dadas.
Ejemplos:
Entrada: A[] = {3, 1, 2, 5}, D[] = {2, 3, 1, 2}
Salida: 7
Explicación: El número entero 7 está presente en todos los AP dados.
Entrada: A[] = {13, 1, 2, 5}, D[] = {5, 10, 1, 12}
Salida: 41
Enfoque: el problema se puede resolver fácilmente usando Hashing . Inicializa una array cnt[] . Para cada elemento de cada AP, incremente el conteo del elemento en la array cnt[] . Devuelve el índice de la array cnt[] con el recuento máximo.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000000
// Function to return element common
// in maximum number of APs
int maxCommonElement(int A[], int D[], int N)
{
// Initialize the count variable
int cnt[MAXN] = { 0 };
for (int i = 0; i < N; i++) {
// Increment count for every
// element of an AP
for (int j = A[i]; j < MAXN; j += D[i])
cnt[j]++;
}
// Find the index with maximum count
int com = max_element(cnt, cnt + MAXN) - cnt;
// Return the maximum common element
return com;
}
// Driver code
int main()
{
int A[] = { 13, 1, 2, 5 },
D[] = { 5, 10, 1, 12 };
int N = sizeof(A) / sizeof(A[0]);
cout << maxCommonElement(A, D, N);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
final static int MAXN = 1000000 ;
static int max_element(int []A, int n)
{
int max = A[0];
for(int i = 0; i < n; i++)
if (A[i] > max )
max = A[i];
return max;
}
// Function to return element common
// in maximum number of APs
static int maxCommonElement(int A[], int D[], int N)
{
// Initialize the count variable
int cnt[] = new int[MAXN] ;
for (int i = 0; i < N; i++)
{
// Increment count for every
// element of an AP
for (int j = A[i]; j < MAXN; j += D[i])
cnt[j]++;
}
// Find the index with maximum count
int ans = 0;
int com = 0;
for(int i = 0; i < MAXN; i++)
{
if (cnt[i] > ans)
{
ans = cnt[i] ;
com = i ;
}
}
// Return the maximum common element
return com;
}
// Driver code
public static void main (String args[])
{
int A[] = { 13, 1, 2, 5 },
D[] = { 5, 10, 1, 12 };
int N = A.length;
System.out.println(maxCommonElement(A, D, N));
}
}
// This code is contributed by AnkitRai01
Python
# Python implementation of the approach MAXN = 1000000 # Function to return element common # in maximum number of APs def maxCommonElement(A, D, N): # Initialize the count variable cnt = [0] * MAXN for i in range(N): # Increment count for every # element of an AP for j in range(A[i], MAXN, D[i]): cnt[j] += 1 # Find the index with maximum count ans = 0 com = 0 for i in range(MAXN): if cnt[i] > ans: ans = cnt[i] com = i # Return the maximum common element return com # Driver code A = [13, 1, 2, 5] D = [5, 10, 1, 12] N = len(A) print(maxCommonElement(A, D, N)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAXN = 1000000 ;
static int max_element(int []A, int n)
{
int max = A[0];
for(int i = 0; i < n; i++)
if (A[i] > max )
max = A[i];
return max;
}
// Function to return element common
// in maximum number of APs
static int maxCommonElement(int []A, int []D, int N)
{
// Initialize the count variable
int []cnt = new int[MAXN] ;
for (int i = 0; i < N; i++)
{
// Increment count for every
// element of an AP
for (int j = A[i]; j < MAXN; j += D[i])
cnt[j]++;
}
// Find the index with maximum count
int ans = 0;
int com = 0;
for(int i = 0; i < MAXN; i++)
{
if (cnt[i] > ans)
{
ans = cnt[i] ;
com = i ;
}
}
// Return the maximum common element
return com;
}
// Driver code
public static void Main ()
{
int []A = { 13, 1, 2, 5 };
int []D = { 5, 10, 1, 12 };
int N = A.Length;
Console.WriteLine(maxCommonElement(A, D, N));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
var MAXN = 1000000;
// Function to return element common
// in maximum number of APs
function maxCommonElement(A, D, N)
{
// Initialize the count variable
var cnt = Array(MAXN).fill(0);
for (var i = 0; i < N; i++) {
// Increment count for every
// element of an AP
for (var j = A[i]; j < MAXN; j += D[i])
cnt[j]++;
}
// Find the index with maximum count
var ans = 0;
var com = 0;
for(var i = 0; i < MAXN; i++)
{
if (cnt[i] > ans)
{
ans = cnt[i] ;
com = i ;
}
}
// Return the maximum common element
return com;
}
// Driver code
var A = [ 13, 1, 2, 5 ],
D = [ 5, 10, 1, 12 ];
var N = A.length;
document.write( maxCommonElement(A, D, N));
// This code is contributed by rutvik_56.
</script>
Producción:
41
Complejidad de tiempo: O(N * 10 6 )
Espacio Auxiliar: O(10 6 )
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA