Dada una array arr[] de longitud N , la tarea es encontrar la longitud de la sub-array más larga con el máximo valor de GCD posible.
Ejemplos:
Entrada: arr[] = {1, 2, 2}
Salida: 2
Aquí todos los sub-arreglos posibles y allí los GCD son:
1) {1} -> 1
2) {2} -> 2
3) {2} -> 2
4) {1, 2} -> 1
5) {2, 2} -> 2
6) {1, 2, 3} -> 1
Aquí, el valor máximo de GCD es 2 y el subarreglo más largo tiene GCD = 2 es {2, 2}.
Por lo tanto, la respuesta es {2, 2}.Entrada: arr[] = {3, 3, 3, 3}
Salida: 4
Enfoque ingenuo: genere todos los subconjuntos posibles y encuentre el GCD de cada uno de ellos individualmente para encontrar el subarreglo más largo. Este enfoque tomará O(N 3 ) tiempo para resolver el problema.
Mejor enfoque: el valor máximo de GCD siempre será igual al número más grande presente en la array. Digamos que el número más grande presente en la array es X. Ahora, la tarea es encontrar el subarreglo más grande que tenga todo X . Lo mismo se puede hacer usando el enfoque de dos puntos . A continuación se muestra el algoritmo:
- Encuentre el número más grande en la array. Llamemos a este número X.
- Ejecutar un bucle desde i = 0
- Si arr[i] != X entonces incrementa i y continúa.
- De lo contrario, inicialice j = i .
- Mientras j < n y arr[j] = X , incremente j .
- Actualice la respuesta como ans = max(ans, j – i) .
- Actualice i como i = j .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of
// the largest subarray with
// maximum possible GCD
int findLength(int* arr, int n)
{
// To store the maximum number
// present in the array
int x = 0;
// Finding the maximum element
for (int i = 0; i < n; i++)
x = max(x, arr[i]);
// To store the final answer
int ans = 0;
// Two pointer
for (int i = 0; i < n; i++) {
if (arr[i] != x)
continue;
// Running a loop from j = i
int j = i;
// Condition for incrementing 'j'
while (arr[j] == x)
j++;
// Updating the answer
ans = max(ans, j - i);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2 };
int n = sizeof(arr) / sizeof(int);
cout << findLength(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the length of
// the largest subarray with
// maximum possible GCD
static int findLength(int []arr, int n)
{
// To store the maximum number
// present in the array
int x = 0;
// Finding the maximum element
for (int i = 0; i < n; i++)
x = Math.max(x, arr[i]);
// To store the final answer
int ans = 0;
// Two pointer
for (int i = 0; i < n; i++)
{
if (arr[i] != x)
continue;
// Running a loop from j = i
int j = i;
// Condition for incrementing 'j'
while (arr[j] == x)
{
j++;
if (j >= n )
break;
}
// Updating the answer
ans = Math.max(ans, j - i);
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 2, 2 };
int n = arr.length;
System.out.println(findLength(arr, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the length of # the largest subarray with # maximum possible GCD def findLength(arr, n) : # To store the maximum number # present in the array x = 0; # Finding the maximum element for i in range(n) : x = max(x, arr[i]); # To store the final answer ans = 0; # Two pointer for i in range(n) : if (arr[i] != x) : continue; # Running a loop from j = i j = i; # Condition for incrementing 'j' while (arr[j] == x) : j += 1; if j >= n : break # Updating the answer ans = max(ans, j - i); return ans; # Driver code if __name__ == "__main__" : arr = [ 1, 2, 2 ]; n = len(arr); print(findLength(arr, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the length of
// the largest subarray with
// maximum possible GCD
static int findLength(int []arr, int n)
{
// To store the maximum number
// present in the array
int x = 0;
// Finding the maximum element
for (int i = 0; i < n; i++)
x = Math.Max(x, arr[i]);
// To store the final answer
int ans = 0;
// Two pointer
for (int i = 0; i < n; i++)
{
if (arr[i] != x)
continue;
// Running a loop from j = i
int j = i;
// Condition for incrementing 'j'
while (arr[j] == x)
{
j++;
if (j >= n )
break;
}
// Updating the answer
ans = Math.Max(ans, j - i);
}
return ans;
}
// Driver code
public static void Main ()
{
int []arr = { 1, 2, 2 };
int n = arr.Length;
Console.WriteLine(findLength(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the length of
// the largest subarray with
// maximum possible GCD
function findLength(arr, n)
{
// To store the maximum number
// present in the array
var x = 0;
// Finding the maximum element
for (var i = 0; i < n; i++)
x = Math.max(x, arr[i]);
// To store the final answer
var ans = 0;
// Two pointer
for (var i = 0; i < n; i++) {
if (arr[i] != x)
continue;
// Running a loop from j = i
var j = i;
// Condition for incrementing 'j'
while (arr[j] == x)
j++;
// Updating the answer
ans = Math.max(ans, j - i);
}
return ans;
}
// Driver code
var arr = [1, 2, 2 ];
var n = arr.length;
document.write( findLength(arr, n));
</script>
2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA