Dado un arreglo arr[] de longitud N , la tarea es encontrar el par de índices más pequeño (i, j) tal que el producto de los elementos en el subarreglo arr[i + 1, j – 1] sea coprimo con el producto del subarreglo arr[0, i] o el del subarreglo arr[j, N] . Si no existe tal par, la impresión “-1” .
Ejemplos:
Entrada: arr[] = {2, 4, 1, 3, 7}
Salida: (0, 2)
Explicación: El producto del subarreglo {arr[1], arr[1]} es 4. El producto del subarreglo derecho = 1 * 3 * 7 = 21. Dado que 4 y 21 son coprimos, imprima el rango (0, 2) como respuesta.Entrada: arr[] = {21, 3, 11, 7, 18}
Salida: (1, 3)
Explicación: El producto del subarreglo {arr[1], arr[2]} es 11. El producto del subarreglo derecho es 7 * 18 = 126. Dado que 11 y 126 son coprimos, imprima el rango (1, 3) como respuesta.
Enfoque ingenuo: el enfoque más simple es iterar a través de cada par posible de índices (i, j) y para cada par, encontrar el producto del subarreglo arr[0, i] y arr[j, N] y verificar si es co- prime con el producto del subarreglo arr[i + 1, j – 1] o no. Si se encuentra que es cierto, imprima ese par de índices. Si no existe tal par, imprima “-1” .
Complejidad temporal: O((N 3 )*log(M)), donde M es el producto de todos los elementos del arreglo.
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar una array auxiliar para almacenar el producto de sufijos de los elementos de la array. Siga los pasos a continuación para resolver el problema:
- Almacene el producto de elementos de sufijo en rightProd[] , donde rightProd[i] almacena el producto de elementos de arr[i], arr[N – 1] .
- Encuentre el producto de todos los elementos en la array como totalProd.
- Recorra la array dada usando la variable i y realice las siguientes operaciones:
- Inicializa una variable, digamos product .
- Iterar a través de la array usando la variable j del rango [i, N – 1] .
- Actualice el producto multiplicando el producto por arr[j] .
- Inicialice leftProduct como total/right_prod[i] .
- Compruebe si el producto es coprimo con uno de los productos izquierdo o derecho o no. Si se determina que es cierto, imprima el par (i – 1, j + 1) y salga del ciclo .
- Después de los pasos anteriores, si no existe tal par, 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 calculate GCD // of two integers int gcd(int a, int b) { if (b == 0) return a; // Recursively calculate GCD return gcd(b, a % b); } // Function to find the lexicographically // smallest pair of indices whose product // is co-prime with the product of the // subarrays on its left and right void findPair(int A[], int N) { // Stores the suffix product // of array elements int right_prod[N]; // Set 0/1 if pair satisfies the // given condition or not int flag = 0; // Initialize array right_prod[] right_prod[N - 1] = A[N - 1]; // Update the suffix product for (int i = N - 2; i >= 0; i--) right_prod[i] = right_prod[i + 1] * A[i]; // Stores product of all elements int total_prod = right_prod[0]; // Stores the product of subarray // in between the pair of indices int product; // Iterate through every pair of // indices (i, j) for (int i = 1; i < N - 1; i++) { product = 1; for (int j = i; j < N - 1; j++) { // Store product of A[i, j] product *= A[j]; // Check if product is co-prime // to product of either the left // or right subarrays if (gcd(product, right_prod[j + 1]) == 1 || gcd(product, total_prod / right_prod[i]) == 1) { flag = 1; cout << "(" << i - 1 << ", " << j + 1 << ")"; break; } } if (flag == 1) break; } // If no such pair is found, // then print -1 if (flag == 0) cout << -1; } // Driver Code int main() { int arr[] = { 2, 4, 1, 3, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call findPair(arr, N); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate GCD // of two integers static int gcd(int a, int b) { if (b == 0) return a; // Recursively calculate GCD return gcd(b, a % b); } // Function to find the lexicographically // smallest pair of indices whose product // is co-prime with the product of the // subarrays on its left and right static void findPair(int A[], int N) { // Stores the suffix product // of array elements int right_prod[] = new int[N]; // Set 0/1 if pair satisfies the // given condition or not int flag = 0; // Initialize array right_prod[] right_prod[N - 1] = A[N - 1]; // Update the suffix product for(int i = N - 2; i >= 0; i--) right_prod[i] = right_prod[i + 1] * A[i]; // Stores product of all elements int total_prod = right_prod[0]; // Stores the product of subarray // in between the pair of indices int product; // Iterate through every pair of // indices (i, j) for(int i = 1; i < N - 1; i++) { product = 1; for(int j = i; j < N - 1; j++) { // Store product of A[i, j] product *= A[j]; // Check if product is co-prime // to product of either the left // or right subarrays if (gcd(product, right_prod[j + 1]) == 1 || gcd(product, total_prod / right_prod[i]) == 1) { flag = 1; System.out.println("(" + (i - 1) + ", " + (j + 1) + ")"); break; } } if (flag == 1) break; } // If no such pair is found, // then print -1 if (flag == 0) System.out.print(-1); } // Driver Code public static void main(String[] args) { int arr[] = { 2, 4, 1, 3, 7 }; int N = arr.length; // Function Call findPair(arr, N); } } // This code is contributed by chitranayal
Python3
# Python3 program for the above approach # Function to calculate GCD # of two integers def gcd(a, b): if (b == 0): return a # Recursively calculate GCD return gcd(b, a % b) # Function to find the lexicographically # smallest pair of indices whose product # is co-prime with the product of the # subarrays on its left and right def findPair(A, N): # Stores the suffix product # of array elements right_prod = [0] * N # Set 0/1 if pair satisfies the # given condition or not flag = 0 # Initialize array right_prod right_prod[N - 1] = A[N - 1] # Update the suffix product for i in range(N - 2, 0, -1): right_prod[i] = right_prod[i + 1] * A[i] # Stores product of all elements total_prod = right_prod[0] # Stores the product of subarray # in between the pair of indices product = 1 # Iterate through every pair of # indices (i, j) for i in range(1, N - 1): product = 1 for j in range(i, N - 1): # Store product of A[i, j] product *= A[j] # Check if product is co-prime # to product of either the left # or right subarrays if (gcd(product, right_prod[j + 1]) == 1 or gcd(product, total_prod / right_prod[i]) == 1): flag = 1 print("(" , (i - 1) , ", " , (j + 1) ,")") break if (flag == 1): break # If no such pair is found, # then print -1 if (flag == 0): print(-1) # Driver Code if __name__ == '__main__': arr = [ 2, 4, 1, 3, 7 ] N = len(arr) # Function Call findPair(arr, N) # This code is contributed by Amit Katiyar
C#
// C# program for the above approach using System; class GFG{ // Function to calculate GCD // of two integers static int gcd(int a, int b) { if (b == 0) return a; // Recursively calculate GCD return gcd(b, a % b); } // Function to find the lexicographically // smallest pair of indices whose product // is co-prime with the product of the // subarrays on its left and right static void findPair(int []A, int N) { // Stores the suffix product // of array elements int []right_prod = new int[N]; // Set 0/1 if pair satisfies the // given condition or not int flag = 0; // Initialize array right_prod[] right_prod[N - 1] = A[N - 1]; // Update the suffix product for(int i = N - 2; i >= 0; i--) right_prod[i] = right_prod[i + 1] * A[i]; // Stores product of all elements int total_prod = right_prod[0]; // Stores the product of subarray // in between the pair of indices int product; // Iterate through every pair of // indices (i, j) for(int i = 1; i < N - 1; i++) { product = 1; for(int j = i; j < N - 1; j++) { // Store product of A[i, j] product *= A[j]; // Check if product is co-prime // to product of either the left // or right subarrays if (gcd(product, right_prod[j + 1]) == 1 || gcd(product, total_prod / right_prod[i]) == 1) { flag = 1; Console.WriteLine("(" + (i - 1) + ", " + (j + 1) + ")"); break; } } if (flag == 1) break; } // If no such pair is found, // then print -1 if (flag == 0) Console.Write(-1); } // Driver Code public static void Main(String[] args) { int []arr = { 2, 4, 1, 3, 7 }; int N = arr.Length; // Function Call findPair(arr, N); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript program for the above approach // Function to calculate GCD // of two integers function gcd(a, b) { if (b == 0) return a; // Recursively calculate GCD return gcd(b, a % b); } // Function to find the lexicographically // smallest pair of indices whose product // is co-prime with the product of the // subarrays on its left and right function findPair(A, N) { // Stores the suffix product // of array elements let right_prod = []; // Set 0/1 if pair satisfies the // given condition or not let flag = 0; // Initialize array right_prod[] right_prod[N - 1] = A[N - 1]; // Update the suffix product for(let i = N - 2; i >= 0; i--) right_prod[i] = right_prod[i + 1] * A[i]; // Stores product of all elements let total_prod = right_prod[0]; // Stores the product of subarray // in between the pair of indices let product; // Iterate through every pair of // indices (i, j) for(let i = 1; i < N - 1; i++) { product = 1; for(let j = i; j < N - 1; j++) { // Store product of A[i, j] product *= A[j]; // Check if product is co-prime // to product of either the left // or right subarrays if (gcd(product, right_prod[j + 1]) == 1 || gcd(product, total_prod / right_prod[i]) == 1) { flag = 1; document.write("(" + (i - 1) + ", " + (j + 1) + ")"); break; } } if (flag == 1) break; } // If no such pair is found, // then print -1 if (flag == 0) document.write(-1); } // Driver code let arr = [ 2, 4, 1, 3, 7 ]; let N = arr.length; // Function Call findPair(arr, N); // This code is contributed by code_hunt </script>
(0, 2)
Complejidad de tiempo: O(N 2 *log(M)), donde M es el producto de todos los elementos del arreglo
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