Dada una array , arr[] de tamaño N , la tarea es contar el número de formas de dividir los elementos de la array en dos subarreglos de modo que el GCD de ambos subarreglos sea igual.
Ejemplos:
Entrada: arr[] = {8, 4, 4, 8, 12}
Salida: 2
Explicación:
Las formas posibles de dividir la array en dos grupos de GCD iguales son: { {{arr[0], arr[1]}, { arr[2], arr[3], arr[4]}}, {{arr[0], arr[1], arr[2]}, {arr[3], arr[4]}} }.
Por lo tanto, la salida requerida es 2.Entrada: arr[] = {1, 2, 4, 6, 5}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, en cada índice de array, dividir la array en dos subarreglos y verificar si el GCD de ambos subarreglos es igual o no. Si se encuentra que es cierto, entonces incremente el conteo de dichos subarreglos. Finalmente, imprima el conteo.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la técnica Prefix Sum Array . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntWays para almacenar la cantidad de formas de dividir la array en dos subarreglos de modo que el GCD de ambos subarreglos sea igual.
- Inicialice una array , diga prefixGCD[] para almacenar el prefijo GCD de los elementos de la array.
- Inicialice una array , diga suffixGCD[] para almacenar el sufijo GCD de los elementos de la array.
- Atraviese las arrays prefixGCD[] y suffixGCD[] utilizando la variable i y verifique si prefixGCD[i] y suffixGCD[i + 1] son iguales o no. Si se determina que es cierto, aumente el valor de cntWays .
- Finalmente, imprima el valor de cntWays .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count number of ways to split // array into two groups with equal GCD value. int cntWaysToSplitArrayTwo(int arr[], int N) { // Stores prefix GCD // of the array int prefixGCD[N]; // Update prefixGCD[0] prefixGCD[0] = arr[0]; // Stores suffix GCD // of the array int suffixGCD[N]; // Update suffixGCD[N - 1] suffixGCD[N - 1] = arr[N - 1]; // Traverse the array for (int i = 1; i < N; i++) { // Update prefixGCD[i] prefixGCD[i] = __gcd(prefixGCD[i - 1], arr[i]); } // Traverse the array for (int i = N - 2; i >= 0; i--) { // Update prefixGCD[i] suffixGCD[i] = __gcd(suffixGCD[i + 1], arr[i]); } // Stores count of ways to split array // into two groups with equal GCD int cntWays = 0; // Traverse prefixGCD[] and suffixGCD[] for (int i = 0; i < N - 1; i++) { // If GCD of both groups equal if (prefixGCD[i] == suffixGCD[i + 1]) { // Update cntWays cntWays += 1; } } return cntWays; } // Driver Code int main() { int arr[] = { 8, 4, 4, 8, 12 }; int N = sizeof(arr) / sizeof(arr[0]); cout << cntWaysToSplitArrayTwo(arr, N); return 0; }
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ 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 count number of ways to split // array into two groups with equal GCD value. static int cntWaysToSplitArrayTwo(int arr[], int N) { // Stores prefix GCD // of the array int prefixGCD[] = new int[N]; // Update prefixGCD[0] prefixGCD[0] = arr[0]; // Stores suffix GCD // of the array int suffixGCD[] = new int[N]; // Update suffixGCD[N - 1] suffixGCD[N - 1] = arr[N - 1]; // Traverse the array for(int i = 1; i < N; i++) { // Update prefixGCD[i] prefixGCD[i] = gcd(prefixGCD[i - 1], arr[i]); } // Traverse the array for(int i = N - 2; i >= 0; i--) { // Update prefixGCD[i] suffixGCD[i] = gcd(suffixGCD[i + 1], arr[i]); } // Stores count of ways to split array // into two groups with equal GCD int cntWays = 0; // Traverse prefixGCD[] and suffixGCD[] for(int i = 0; i < N - 1; i++) { // If GCD of both groups equal if (prefixGCD[i] == suffixGCD[i + 1]) { // Update cntWays cntWays += 1; } } return cntWays; } // Driver Code public static void main(String[] args) { int arr[] = { 8, 4, 4, 8, 12 }; int N = arr.length; System.out.print(cntWaysToSplitArrayTwo(arr, N)); } } // This code is contributed by sanjoy_62
Python3
# Python3 program to implement # the above approach import math # Function to count number of ways to split # array into two groups with equal GCD value. def cntWaysToSplitArrayTwo(arr, N): # Stores prefix GCD # of the array prefixGCD = [0] * N # Update prefixGCD[0] prefixGCD[0] = arr[0] # Stores suffix GCD # of the array suffixGCD = [0] * N # Update suffixGCD[N - 1] suffixGCD[N - 1] = arr[N - 1] # Traverse the array for i in range(N): # Update prefixGCD[i] prefixGCD[i] = math.gcd(prefixGCD[i - 1], arr[i]) # Traverse the array for i in range(N - 2, -1, -1): # Update prefixGCD[i] suffixGCD[i] = math.gcd(suffixGCD[i + 1], arr[i]) # Stores count of ways to split array # into two groups with equal GCD cntWays = 0 # Traverse prefixGCD[] and suffixGCD[] for i in range(N - 1): # If GCD of both groups equal if (prefixGCD[i] == suffixGCD[i + 1]): # Update cntWays cntWays += 1 return cntWays # Driver Code arr = [ 8, 4, 4, 8, 12 ] N = len(arr) print(cntWaysToSplitArrayTwo(arr, N)) # This code is contributed by susmitakundugoaldanga
C#
// C# program to implement // the above approach using System; class GFG{ 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 count number of ways to split // array into two groups with equal GCD value. static int cntWaysToSplitArrayTwo(int []arr, int N) { // Stores prefix GCD // of the array int []prefixGCD = new int[N]; // Update prefixGCD[0] prefixGCD[0] = arr[0]; // Stores suffix GCD // of the array int []suffixGCD = new int[N]; // Update suffixGCD[N - 1] suffixGCD[N - 1] = arr[N - 1]; // Traverse the array for(int i = 1; i < N; i++) { // Update prefixGCD[i] prefixGCD[i] = gcd(prefixGCD[i - 1], arr[i]); } // Traverse the array for(int i = N - 2; i >= 0; i--) { // Update prefixGCD[i] suffixGCD[i] = gcd(suffixGCD[i + 1], arr[i]); } // Stores count of ways to split array // into two groups with equal GCD int cntWays = 0; // Traverse prefixGCD[] and suffixGCD[] for(int i = 0; i < N - 1; i++) { // If GCD of both groups equal if (prefixGCD[i] == suffixGCD[i + 1]) { // Update cntWays cntWays += 1; } } return cntWays; } // Driver Code public static void Main(String[] args) { int []arr = { 8, 4, 4, 8, 12 }; int N = arr.Length; Console.Write(cntWaysToSplitArrayTwo(arr, N)); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript program to implement // the above approach function gcd(a, 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 count number of ways to split // array into two groups with equal GCD value. function cntWaysToSplitArrayTwo(arr, N) { // Stores prefix GCD // of the array let prefixGCD = []; // Update prefixGCD[0] prefixGCD[0] = arr[0]; // Stores suffix GCD // of the array let suffixGCD = []; // Update suffixGCD[N - 1] suffixGCD[N - 1] = arr[N - 1]; // Traverse the array for(let i = 1; i < N; i++) { // Update prefixGCD[i] prefixGCD[i] = gcd(prefixGCD[i - 1], arr[i]); } // Traverse the array for(let i = N - 2; i >= 0; i--) { // Update prefixGCD[i] suffixGCD[i] = gcd(suffixGCD[i + 1], arr[i]); } // Stores count of ways to split array // into two groups with equal GCD let cntWays = 0; // Traverse prefixGCD[] and suffixGCD[] for(let i = 0; i < N - 1; i++) { // If GCD of both groups equal if (prefixGCD[i] == suffixGCD[i + 1]) { // Update cntWays cntWays += 1; } } return cntWays; } // Driver code let arr = [ 8, 4, 4, 8, 12 ]; let N = arr.length; document.write(cntWaysToSplitArrayTwo(arr, N)); // This code is contributed by code_hunt </script>
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)