Dado un arreglo arr[] que consta de N enteros, la tarea es encontrar el índice máximo K tal que el producto de los subarreglos {arr[0], arr[K]} y {arr[K + 1], arr[N – 1]} son coprimos . Si no existe tal índice, imprima “-1” .
Ejemplos:
Entrada: arr[] = {2, 3, 4, 5}
Salida: 2
Explicación:
El índice más pequeño para la partición es 2.
El producto del subarreglo izquierdo es = 2 * 3 * 4 = 24.
El producto del subarreglo derecho = 5.
Desde 24 y 5 son coprimos, la respuesta requerida es 2.Entrada: arr[] = {23, 41, 52, 83, 7, 13}
Salida: 0
Explicación:
el índice más pequeño para la partición es 0.
Producto del subarreglo izquierdo = 23.
Producto del subarreglo derecho = 41 * 52 * 83 * 7 * 13 = 16102996.
Dado que 23 y 16102996 son coprimos, la respuesta es 0.
Enfoque ingenuo: el enfoque más simple es verificar todos los índices posibles de partición desde el inicio de la array y verificar si el producto de los subarreglos formados es coprimo o no. Si existe tal índice, imprima ese índice. De lo contrario, imprima “-1” .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la array de productos de prefijos y la array de productos de sufijos y encontrar el índice posible. Siga los pasos a continuación para resolver el problema:
- Cree dos arrays auxiliares, prefijo[] y sufijo[] para almacenar el producto de array de prefijo y sufijo. Inicialice el prefijo[0] en arr[0] y el sufijo[N – 1] en arr[N – 1] .
- Recorra la array dada sobre el rango [2, N] usando la variable i y actualice la array de prefijos como prefix[i] = prefix[i – 1]*arr[i] .
- Recorra la array dada desde atrás sobre el rango [N – 2, 0] usando la variable i y actualice la array de sufijos como sufijo[i] = sufijo[i + 1]*arr[i] .
- Itere un ciclo sobre el rango [0, N – 1] usando la variable i y verifique si el prefijo [i] y el sufijo [i + 1] son coprimos o no . Si se determina que es cierto, imprime el índice actual y sale del bucle .
- Si no existe tal índice en el paso anterior, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the GCD of 2 numbers
int GCD(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Find the GCD recursively
return GCD(b, a % b);
}
// Function to find the minimum partition
// index K s.t. product of both subarrays
// around that partition are co-prime
int findPartition(int nums[], int N)
{
// Stores the prefix and suffix
// array product
int prefix[N], suffix[N], i, k;
prefix[0] = nums[0];
// Update the prefix array
for (i = 1; i < N; i++) {
prefix[i] = prefix[i - 1]
* nums[i];
}
suffix[N - 1] = nums[N - 1];
// Update the suffix array
for (i = N - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1]
* nums[i];
}
// Iterate the given array
for (k = 0; k < N - 1; k++) {
// Check if prefix[k] and
// suffix[k+1] are co-prime
if (GCD(prefix[k],
suffix[k + 1])
== 1) {
return k;
}
}
// If no index for partition
// exists, then return -1
return -1;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << findPartition(arr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class solution{
// Function to find the
// GCD of 2 numbers
static int GCD(int a,
int b)
{
// Base Case
if (b == 0)
return a;
// Find the GCD
// recursively
return GCD(b, a % b);
}
// Function to find the minimum
// partition index K s.t. product
// of both subarrays around that
// partition are co-prime
static int findPartition(int nums[],
int N)
{
// Stores the prefix and
// suffix array product
int []prefix = new int[N];
int []suffix = new int[N];
int i, k;
prefix[0] = nums[0];
// Update the prefix array
for (i = 1; i < N; i++)
{
prefix[i] = prefix[i - 1] *
nums[i];
}
suffix[N - 1] = nums[N - 1];
// Update the suffix array
for (i = N - 2; i >= 0; i--)
{
suffix[i] = suffix[i + 1] *
nums[i];
}
// Iterate the given array
for (k = 0; k < N - 1; k++)
{
// Check if prefix[k] and
// suffix[k+1] are co-prime
if (GCD(prefix[k],
suffix[k + 1]) == 1)
{
return k;
}
}
// If no index for partition
// exists, then return -1
return -1;
}
// Driver Code
public static void main(String args[])
{
int arr[] = {2, 3, 4, 5};
int N = arr.length;
// Function call
System.out.println(findPartition(arr, N));
}
}
// This code is contributed by SURENDRA_GANGWAR
Python3
# Python3 program for the # above approach # Function to find the # GCD of 2 numbers def GCD(a, b): # Base Case if (b == 0): return a # Find the GCD recursively return GCD(b, a % b) # Function to find the minimum # partition index K s.t. product # of both subarrays around that # partition are co-prime def findPartition(nums, N): #Stores the prefix and # suffix array product prefix=[0] * N suffix=[0] * N prefix[0] = nums[0] # Update the prefix # array for i in range(1, N): prefix[i] = (prefix[i - 1] * nums[i]) suffix[N - 1] = nums[N - 1] # Update the suffix array for i in range(N - 2, -1, -1): suffix[i] = (suffix[i + 1] * nums[i]) # Iterate the given array for k in range(N - 1): # Check if prefix[k] and # suffix[k+1] are co-prime if (GCD(prefix[k], suffix[k + 1]) == 1): return k # If no index for partition # exists, then return -1 return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 5] N = len(arr) # Function call print(findPartition(arr, N)) # This code is contributed by Mohit Kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to find the
// GCD of 2 numbers
static int GCD(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Find the GCD
// recursively
return GCD(b, a % b);
}
// Function to find the minimum
// partition index K s.t. product
// of both subarrays around that
// partition are co-prime
static int findPartition(int[] nums,
int N)
{
// Stores the prefix and
// suffix array product
int[] prefix = new int[N];
int[] suffix = new int[N];
int i, k;
prefix[0] = nums[0];
// Update the prefix array
for (i = 1; i < N; i++)
{
prefix[i] = prefix[i - 1] *
nums[i];
}
suffix[N - 1] = nums[N - 1];
// Update the suffix array
for (i = N - 2; i >= 0; i--)
{
suffix[i] = suffix[i + 1] *
nums[i];
}
// Iterate the given array
for (k = 0; k < N - 1; k++)
{
// Check if prefix[k] and
// suffix[k+1] are co-prime
if (GCD(prefix[k],
suffix[k + 1]) == 1)
{
return k;
}
}
// If no index for partition
// exists, then return -1
return -1;
}
// Driver code
static void Main()
{
int[] arr = {2, 3, 4, 5};
int N = arr.Length;
// Function call
Console.WriteLine(findPartition(arr, N));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program for the above approach
// Function to find the GCD of 2 numbers
function GCD(a, b)
{
// Base Case
if (b == 0)
return a;
// Find the GCD recursively
return GCD(b, a % b);
}
// Function to find the minimum partition
// index K s.t. product of both subarrays
// around that partition are co-prime
function findPartition(nums, N)
{
// Stores the prefix and suffix
// array product
var prefix = Array(N), suffix = Array(N), i, k;
prefix[0] = nums[0];
// Update the prefix array
for (i = 1; i < N; i++) {
prefix[i] = prefix[i - 1]
* nums[i];
}
suffix[N - 1] = nums[N - 1];
// Update the suffix array
for (i = N - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1]
* nums[i];
}
// Iterate the given array
for (k = 0; k < N - 1; k++) {
// Check if prefix[k] and
// suffix[k+1] are co-prime
if (GCD(prefix[k],
suffix[k + 1])
== 1) {
return k;
}
}
// If no index for partition
// exists, then return -1
return -1;
}
// Driver Code
var arr = [2, 3, 4, 5];
var N = arr.length;
// Function call
document.write( findPartition(arr, N));
</script>
2
Complejidad de tiempo: O(N log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA