Dado un arreglo arr[] de N elementos, la tarea es encontrar la longitud del subarreglo más pequeño de manera que cuando este subarreglo se elimine del arreglo, el GCD del arreglo resultante sea máximo.
Nota: la array resultante no debe estar vacía.
Ejemplos:
Entrada: N = 4, arr[] = {3, 6, 1, 2}
Salida: 2
Explicación:
Si eliminamos el subarreglo {1, 2} entonces el subarreglo resultante será {3, 6} y el GCD de este es 3 que es el valor máximo posible.
Entrada: N = 3, arr[] = {4, 8, 4}
Salida: 0
Explicación:
Aquí no necesitamos eliminar ningún subarreglo y el GCD máximo posible es 4.
Enfoque: Se sabe que MCD es una función no creciente. Es decir, si agregamos elementos en la array, entonces el gcd disminuirá o permanecerá constante. Por lo tanto, la idea es usar este concepto para resolver este problema:
- Ahora debemos notar que después de eliminar un subarreglo, el subarreglo resultante debe tener el primer o el último elemento o ambos elementos. Esto se debe a que debemos asegurarnos de que el conjunto resultante después de eliminar el subarreglo no esté vacío. Por lo tanto, no podemos eliminar todos los elementos.
- Entonces, el GCD máximo posible será max(A[0], A[N – 1]) .
- Ahora tenemos que minimizar la longitud del subarreglo que necesitamos eliminar para obtener esta respuesta.
- Para ello, utilizaremos la técnica de dos punteros , apuntando al primer y último elemento respectivamente.
- Ahora aumentaremos el primer puntero si el elemento es divisible por ese mcd y disminuiremos el último puntero si el elemento es divisible por mcd ya que no afectará nuestra respuesta.
- Entonces, finalmente, el número de elementos entre los dos punteros será la longitud del subarreglo que debemos eliminar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
int GetMinSubarrayLength(int a[], int n)
{
// Store the maximum possible
// GCD of the resulting subarray
int ans = max(a[0], a[n - 1]);
// Two pointers initially pointing
// to the first and last element
// respectively
int lo = 0, hi = n - 1;
// Moving the left pointer to the
// right if the elements are
// divisible by the maximum GCD
while (lo < n and a[lo] % ans == 0)
lo++;
// Moving the right pointer to the
// left if the elements are
// divisible by the maximum GCD
while (hi > lo and a[hi] % ans == 0)
hi--;
// Return the length of
// the subarray
return (hi - lo + 1);
}
// Driver code
int main()
{
int arr[] = { 4, 8, 2, 1, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
int length = GetMinSubarrayLength(arr, N);
cout << length << "\n";
return 0;
}
Java
// Java program to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
class GFG {
// Function to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
static int GetMinSubarrayLength(int a[], int n)
{
// Store the maximum possible
// GCD of the resulting subarray
int ans = Math.max(a[0], a[n - 1]);
// Two pointers initially pointing
// to the first and last element
// respectively
int lo = 0, hi = n - 1;
// Moving the left pointer to the
// right if the elements are
// divisible by the maximum GCD
while (lo < n && a[lo] % ans == 0)
lo++;
// Moving the right pointer to the
// left if the elements are
// divisible by the maximum GCD
while (hi > lo && a[hi] % ans == 0)
hi--;
// Return the length of
// the subarray
return (hi - lo + 1);
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 4, 8, 2, 1, 4 };
int N = arr.length;
int Length = GetMinSubarrayLength(arr, N);
System.out.println(Length);
}
}
// This code is contributed by Yash_R
Python3
# Python3 program to find the length of # the smallest subarray that must be # removed in order to maximise the GCD # Function to find the length of # the smallest subarray that must be # removed in order to maximise the GCD def GetMinSubarrayLength(a, n): # Store the maximum possible # GCD of the resulting subarray ans = max(a[0], a[n - 1]) # Two pointers initially pointing # to the first and last element # respectively lo = 0 hi = n - 1 # Moving the left pointer to the # right if the elements are # divisible by the maximum GCD while (lo < n and a[lo] % ans == 0): lo += 1 # Moving the right pointer to the # left if the elements are # divisible by the maximum GCD while (hi > lo and a[hi] % ans == 0): hi -= 1 # Return the length of # the subarray return (hi - lo + 1) # Driver code if __name__ == '__main__': arr = [4, 8, 2, 1, 4] N = len(arr) length = GetMinSubarrayLength(arr, N) print(length) # This code is contributed by mohit kumar 29
C#
// C# program to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
using System;
class GFG {
// Function to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
static int GetMinSubarrayLength(int []a, int n)
{
// Store the maximum possible
// GCD of the resulting subarray
int ans = Math.Max(a[0], a[n - 1]);
// Two pointers initially pointing
// to the first and last element
// respectively
int lo = 0, hi = n - 1;
// Moving the left pointer to the
// right if the elements are
// divisible by the maximum GCD
while (lo < n && a[lo] % ans == 0)
lo++;
// Moving the right pointer to the
// left if the elements are
// divisible by the maximum GCD
while (hi > lo && a[hi] % ans == 0)
hi--;
// Return the length of
// the subarray
return (hi - lo + 1);
}
// Driver code
public static void Main (string[] args)
{
int []arr = { 4, 8, 2, 1, 4 };
int N = arr.Length;
int Length = GetMinSubarrayLength(arr, N);
Console.WriteLine(Length);
}
}
// This code is contributed by Yash_R
Javascript
<script>
// Javascript program to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
// Function to find the length of
// the smallest subarray that must be
// removed in order to maximise the GCD
function GetMinSubarrayLength(a, n)
{
// Store the maximum possible
// GCD of the resulting subarray
var ans = Math.max(a[0], a[n - 1]);
// Two pointers initially pointing
// to the first and last element
// respectively
var lo = 0, hi = n - 1;
// Moving the left pointer to the
// right if the elements are
// divisible by the maximum GCD
while (lo < n && a[lo] % ans == 0)
lo++;
// Moving the right pointer to the
// left if the elements are
// divisible by the maximum GCD
while (hi > lo && a[hi] % ans == 0)
hi--;
// Return the length of
// the subarray
return (hi - lo + 1);
}
// Driver code
var arr = [4, 8, 2, 1, 4 ];
var N = arr.length;
var length = GetMinSubarrayLength(arr, N);
document.write( length );
// This code is contributed by itsok.
</script>
Producción:
2
Complejidad de tiempo: O(N)