El par de índices más pequeño con el producto del subarreglo coprimo con el producto del subarreglo a la izquierda o a la derecha

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>
Producción: 

(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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *