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>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)