Dado un arreglo arr[] que consta de N enteros, la tarea es encontrar la longitud máxima del subarreglo que tiene el Máximo Común Divisor (MCD) de todos los elementos mayores que 1 .
Ejemplos:
Entrada: arr[] = {4, 3, 2, 2}
Salida: 2
Explicación:
Considere el subarreglo {2, 2} que tiene GCD como 2(> 1) que es de longitud máxima.Entrada: arr[] = {410, 52, 51, 180, 222, 33, 33}
Salida: 5
Enfoque ingenuo: el problema dado se puede resolver generando todos los subarreglos posibles de la array dada y realizar un seguimiento de la longitud máxima del subarreglo con GCD mayor que 1. Después de verificar todos los subarreglos, imprima la longitud máxima obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find maximum length of // the subarray having GCD > one void maxSubarrayLen(int arr[], int n) { // Stores maximum length of subarray int maxLen = 0; // Loop to iterate over all subarrays // starting from index i for (int i = 0; i < n; i++) { // Find the GCD of subarray // from i to j int gcd = 0; for (int j = i; j < n; j++) { // Calculate GCD gcd = __gcd(gcd, arr[j]); // Update maximum length // of the subarray if (gcd > 1) maxLen = max(maxLen, j - i + 1); else break; } } // Print maximum length cout << maxLen; } // Driver Code int main() { int arr[] = { 410, 52, 51, 180, 222, 33, 33 }; int N = sizeof(arr) / sizeof(int); maxSubarrayLen(arr, N); return 0; }
Java
// Java code for above approach import java.util.*; class GFG{ // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to find maximum length of // the subarray having GCD > one static void maxSubarrayLen(int arr[], int n) { // Stores maximum length of subarray int maxLen = 0; // Loop to iterate over all subarrays // starting from index i for (int i = 0; i < n; i++) { // Find the GCD of subarray // from i to j int gcd = 0; for (int j = i; j < n; j++) { // Calculate GCD gcd = __gcd(gcd, arr[j]); // Update maximum length // of the subarray if (gcd > 1) maxLen = Math.max(maxLen, j - i + 1); else break; } } // Print maximum length System.out.print(maxLen); } // Driver Code public static void main(String[] args) { int arr[] = { 410, 52, 51, 180, 222, 33, 33 }; int N = arr.length; maxSubarrayLen(arr, N); } } // This code is contributed by avijitmondal1998.
Python3
# Python program of the above approach def __gcd(a, b): if (b == 0): return a; return __gcd(b, a % b); # Function to find maximum length of # the subarray having GCD > one def maxSubarrayLen(arr, n) : # Stores maximum length of subarray maxLen = 0; # Loop to iterate over all subarrays # starting from index i for i in range(n): # Find the GCD of subarray # from i to j gcd = 0; for j in range(i, n): # Calculate GCD gcd = __gcd(gcd, arr[j]); # Update maximum length # of the subarray if (gcd > 1): maxLen = max(maxLen, j - i + 1); else: break; # Print maximum length print(maxLen); # Driver Code arr = [410, 52, 51, 180, 222, 33, 33]; N = len(arr) maxSubarrayLen(arr, N); # This code is contributed by gfgking.
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find maximum length of // the subarray having GCD > one static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } static void maxSubarrayLen(int []arr, int n) { // Stores maximum length of subarray int maxLen = 0; // Loop to iterate over all subarrays // starting from index i for (int i = 0; i < n; i++) { // Find the GCD of subarray // from i to j int gcd = 0; for (int j = i; j < n; j++) { // Calculate GCD gcd = __gcd(gcd, arr[j]); // Update maximum length // of the subarray if (gcd > 1) maxLen = Math.Max(maxLen, j - i + 1); else break; } } // Print maximum length Console.Write(maxLen); } // Driver Code static public void Main (){ int []arr = { 410, 52, 51, 180, 222, 33, 33 }; int N = arr.Length; maxSubarrayLen(arr, N); } } // This code is contributed by Potta Lokesh
Javascript
<script> // Javascript program of the above approach function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to find maximum length of // the subarray having GCD > one function maxSubarrayLen(arr, n) { // Stores maximum length of subarray let maxLen = 0; // Loop to iterate over all subarrays // starting from index i for (let i = 0; i < n; i++) { // Find the GCD of subarray // from i to j let gcd = 0; for (let j = i; j < n; j++) { // Calculate GCD gcd = __gcd(gcd, arr[j]); // Update maximum length // of the subarray if (gcd > 1) maxLen = Math.max(maxLen, j - i + 1); else break; } } // Print maximum length document.write(maxLen); } // Driver Code let arr = [410, 52, 51, 180, 222, 33, 33]; let N = arr.length; maxSubarrayLen(arr, N); // This code is contributed by _saurabh_jaiswal. </script>
5
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: lo anterior también se puede optimizar utilizando la técnica de ventana deslizante y el árbol de segmentos . Supongamos que L denota el primer índice, R denota el último índice y X denota el tamaño de la ventana actual, entonces hay dos casos posibles como se explica a continuación:
- El GCD de la ventana actual es 1 . En este caso, pase a la siguiente ventana de tamaño X (es decir, L + 1 a R + 1 ).
- El GCD de la ventana actual es mayor que 1 . En este caso, aumente el tamaño de la ventana actual en uno (es decir, L a R + 1 ).
Por lo tanto, para implementar la idea anterior, se puede usar un árbol de segmentos para encontrar el GCD de los rangos de índice dados de la array de manera eficiente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to build the Segment Tree // from the given array to process // range queries in log(N) time void build_tree(int* b, vector<int>& seg_tree, int l, int r, int vertex) { // Termination Condition if (l == r) { seg_tree[vertex] = b[l]; return; } // Find the mid value int mid = (l + r) / 2; // Left and Right Recursive Call build_tree(b, seg_tree, l, mid, 2 * vertex); build_tree(b, seg_tree, mid + 1, r, 2 * vertex + 1); // Update the Segment Tree Node seg_tree[vertex] = __gcd(seg_tree[2 * vertex], seg_tree[2 * vertex + 1]); } // Function to return the GCD of the // elements of the Array from index // l to index r int range_gcd(vector<int>& seg_tree, int v, int tl, int tr, int l, int r) { // Base Case if (l > r) return 0; if (l == tl && r == tr) return seg_tree[v]; // Find the middle range int tm = (tl + tr) / 2; // Find the GCD and return return __gcd( range_gcd(seg_tree, 2 * v, tl, tm, l, min(tm, r)), range_gcd(seg_tree, 2 * v + 1, tm + 1, tr, max(tm + 1, l), r)); } // Function to print maximum length of // the subarray having GCD > one void maxSubarrayLen(int arr[], int n) { // Stores the Segment Tree vector<int> seg_tree(4 * (n) + 1, 0); // Function call to build the // Segment tree from array arr[] build_tree(arr, seg_tree, 0, n - 1, 1); // Store maximum length of subarray int maxLen = 0; // Starting and ending pointer of // the current window int l = 0, r = 0; while (r < n && l < n) { // Case where the GCD of the // current window is 1 if (range_gcd(seg_tree, 1, 0, n - 1, l, r) == 1) { l++; } // Update the maximum length maxLen = max(maxLen, r - l + 1); r++; } // Print answer cout << maxLen; } // Driver Code int main() { int arr[] = { 410, 52, 51, 180, 222, 33, 33 }; int N = sizeof(arr) / sizeof(int); maxSubarrayLen(arr, N); return 0; }
Java
// Java program of the above approach class GFG{ // Function to build the Segment Tree // from the given array to process // range queries in log(N) time static void build_tree(int[] b, int [] seg_tree, int l, int r, int vertex) { // Termination Condition if (l == r) { seg_tree[vertex] = b[l]; return; } // Find the mid value int mid = (l + r) / 2; // Left and Right Recursive Call build_tree(b, seg_tree, l, mid, 2 * vertex); build_tree(b, seg_tree, mid + 1, r, 2 * vertex + 1); // Update the Segment Tree Node seg_tree[vertex] = __gcd(seg_tree[2 * vertex], seg_tree[2 * vertex + 1]); } static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); } // Function to return the GCD of the // elements of the Array from index // l to index r static int range_gcd(int [] seg_tree, int v, int tl, int tr, int l, int r) { // Base Case if (l > r) return 0; if (l == tl && r == tr) return seg_tree[v]; // Find the middle range int tm = (tl + tr) / 2; // Find the GCD and return return __gcd( range_gcd(seg_tree, 2 * v, tl, tm, l, Math.min(tm, r)), range_gcd(seg_tree, 2 * v + 1, tm + 1, tr, Math.max(tm + 1, l), r)); } // Function to print maximum length of // the subarray having GCD > one static void maxSubarrayLen(int arr[], int n) { // Stores the Segment Tree int []seg_tree = new int[4 * (n) + 1]; // Function call to build the // Segment tree from array arr[] build_tree(arr, seg_tree, 0, n - 1, 1); // Store maximum length of subarray int maxLen = 0; // Starting and ending pointer of // the current window int l = 0, r = 0; while (r < n && l < n) { // Case where the GCD of the // current window is 1 if (range_gcd(seg_tree, 1, 0, n - 1, l, r) == 1) { l++; } // Update the maximum length maxLen = Math.max(maxLen, r - l + 1); r++; } // Print answer System.out.print(maxLen); } // Driver Code public static void main(String[] args) { int arr[] = { 410, 52, 51, 180, 222, 33, 33 }; int N = arr.length; maxSubarrayLen(arr, N); } } // This code is contributed by shikhasingrajput
Python3
# Python3 program of the above approach # Function to build the Segment Tree # from the given array to process # range queries in log(N) time def build_tree(b, seg_tree, l, r, vertex): # Termination Condition if (l == r): seg_tree[vertex] = b[l] return # Find the mid value mid = int((l + r) / 2) # Left and Right Recursive Call build_tree(b, seg_tree, l, mid, 2 * vertex) build_tree(b, seg_tree, mid + 1, r, 2 * vertex + 1) # Update the Segment Tree Node seg_tree[vertex] = __gcd(seg_tree[2 * vertex], seg_tree[2 * vertex + 1]) def __gcd(a, b): if b == 0: return b else: return __gcd(b, a % b) # Function to return the GCD of the # elements of the Array from index # l to index r def range_gcd(seg_tree, v, tl, tr, l, r): # Base Case if (l > r): return 0 if (l == tl and r == tr): return seg_tree[v] # Find the middle range tm = int((tl + tr) / 2) # Find the GCD and return return __gcd(range_gcd(seg_tree, 2 * v, tl, tm, l, min(tm, r)), range_gcd(seg_tree, 2 * v + 1, tm + 1, tr, max(tm + 1, l), r)) # Function to print maximum length of # the subarray having GCD > one def maxSubarrayLen(arr, n): # Stores the Segment Tree seg_tree = [0]*(4*n + 1) # Function call to build the # Segment tree from array []arr build_tree(arr, seg_tree, 0, n - 1, 1) # Store maximum length of subarray maxLen = 0 # Starting and ending pointer of # the current window l, r = 0, 0 while (r < n and l < n): # Case where the GCD of the # current window is 1 if (range_gcd(seg_tree, 1, 0, n - 1, l, r) == 1): l+=1 # Update the maximum length maxLen = max(maxLen, r - l - 1) r+=1 # Print answer print(maxLen, end = "") arr = [ 410, 52, 51, 180, 222, 33, 33 ] N = len(arr) maxSubarrayLen(arr, N) # This code is contributed by divyesh072019.
C#
// C# program of the above approach using System; public class GFG { // Function to build the Segment Tree // from the given array to process // range queries in log(N) time static void build_tree(int[] b, int [] seg_tree, int l, int r, int vertex) { // Termination Condition if (l == r) { seg_tree[vertex] = b[l]; return; } // Find the mid value int mid = (l + r) / 2; // Left and Right Recursive Call build_tree(b, seg_tree, l, mid, 2 * vertex); build_tree(b, seg_tree, mid + 1, r, 2 * vertex + 1); // Update the Segment Tree Node seg_tree[vertex] = __gcd(seg_tree[2 * vertex], seg_tree[2 * vertex + 1]); } static int __gcd(int a, int b) { return b == 0? a:__gcd(b, a % b); } // Function to return the GCD of the // elements of the Array from index // l to index r static int range_gcd(int [] seg_tree, int v, int tl, int tr, int l, int r) { // Base Case if (l > r) return 0; if (l == tl && r == tr) return seg_tree[v]; // Find the middle range int tm = (tl + tr) / 2; // Find the GCD and return return __gcd( range_gcd(seg_tree, 2 * v, tl, tm, l, Math.Min(tm, r)), range_gcd(seg_tree, 2 * v + 1, tm + 1, tr, Math.Max(tm + 1, l), r)); } // Function to print maximum length of // the subarray having GCD > one static void maxSubarrayLen(int []arr, int n) { // Stores the Segment Tree int []seg_tree = new int[4 * (n) + 1]; // Function call to build the // Segment tree from array []arr build_tree(arr, seg_tree, 0, n - 1, 1); // Store maximum length of subarray int maxLen = 0; // Starting and ending pointer of // the current window int l = 0, r = 0; while (r < n && l < n) { // Case where the GCD of the // current window is 1 if (range_gcd(seg_tree, 1, 0, n - 1, l, r) == 1) { l++; } // Update the maximum length maxLen = Math.Max(maxLen, r - l + 1); r++; } // Print answer Console.Write(maxLen); } // Driver Code public static void Main(String[] args) { int []arr = { 410, 52, 51, 180, 222, 33, 33 }; int N = arr.Length; maxSubarrayLen(arr, N); } } // This code is contributed by shikhasingrajput
Javascript
<script> // Javascript program of the above approach function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to build the Segment Tree // from the given array to process // range queries in log(N) time function build_tree(b, seg_tree, l, r, vertex) { // Termination Condition if (l == r) { seg_tree[vertex] = b[l]; return; } // Find the mid value let mid = Math.floor((l + r) / 2); // Left and Right Recursive Call build_tree(b, seg_tree, l, mid, 2 * vertex); build_tree(b, seg_tree, mid + 1, r, 2 * vertex + 1); // Update the Segment Tree Node seg_tree[vertex] = __gcd(seg_tree[2 * vertex], seg_tree[2 * vertex + 1]); } // Function to return the GCD of the // elements of the Array from index // l to index r function range_gcd(seg_tree, v, tl, tr, l, r) { // Base Case if (l > r) return 0; if (l == tl && r == tr) return seg_tree[v]; // Find the middle range let tm = Math.floor((tl + tr) / 2); // Find the GCD and return return __gcd( range_gcd(seg_tree, 2 * v, tl, tm, l, Math.min(tm, r)), range_gcd(seg_tree, 2 * v + 1, tm + 1, tr, Math.max(tm + 1, l), r) ); } // Function to print maximum length of // the subarray having GCD > one function maxSubarrayLen(arr, n) { // Stores the Segment Tree let seg_tree = new Array(4 * n + 1).fill(0); // Function call to build the // Segment tree from array arr[] build_tree(arr, seg_tree, 0, n - 1, 1); // Store maximum length of subarray let maxLen = 0; // Starting and ending pointer of // the current window let l = 0, r = 0; while (r < n && l < n) { // Case where the GCD of the // current window is 1 if (range_gcd(seg_tree, 1, 0, n - 1, l, r) == 1) { l++; } // Update the maximum length maxLen = Math.max(maxLen, r - l + 1); r++; } // Print answer document.write(maxLen); } // Driver Code let arr = [410, 52, 51, 180, 222, 33, 33]; let N = arr.length; maxSubarrayLen(arr, N); // This code is contributed by gfgking. </script>
5
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por satyamkant2805 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA