Índice más pequeño que divide una array en dos subarreglos con el mismo producto

Dada una array (indexación basada en 1) arr[] que consta de N enteros distintos de cero, la tarea es encontrar el índice más a la izquierda i tal que el producto de todos los elementos de los subarreglos arr[1, i] y arr[i + 1, N] es lo mismo.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 3, 2, 1}
Salida: 3
Explicación: el índice 3 genera el subarreglo {arr[1], arr[3]} con el producto 6 (= 1 * 2 * 3) y {arr[4], arr[6]} con producto 6 ( = 3 * 2 * 1).

Entrada: arr = {3, 2, 6}
Salida: 2

Enfoque: siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos producto , > que almacene el producto de todos los elementos de la array.
• Recorra la array dada y encuentre el producto de todos los elementos de la array, guárdelo en el producto .
• Inicializa dos variables izquierda y derecha a 1 que almacena el producto del subarreglo izquierdo y derecho
• Recorra la array dada y realice los siguientes pasos:
  • Multiplique el valor de left por arr[i] .
  • Divide el valor de right por arr[i] .
  • Si el valor de la izquierda es igual a la derecha , imprima el valor del índice actual i como el índice resultante y salga del ciclo .
• Después de completar los pasos anteriores, si no existe dicho índice, imprima «-1» como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to find the smallest
// index that splits the array into
// two subarrays with equal product
void prodEquilibrium(int arr[], int N)
{
    // Stores the product of the array
    int product = 1;
 
    // Traverse the given array
    for (int i = 0; i < N; i++) {
        product *= arr[i];
    }
 
    // Stores the product of left
    // and the right subarrays
    int left = 1;
    int right = product;
 
    // Traverse the given array
    for (int i = 0; i < N; i++) {
 
        // Update the products
        left = left * arr[i];
        right = right / arr[i];
 
        // Check if product is equal
        if (left == right) {
 
            // Print resultant index
            cout << i + 1 << endl;
            return;
        }
    }
 
    // If no partition exists, then
    // print -1.
    cout << -1 << endl;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 3, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    prodEquilibrium(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the smallest
// index that splits the array into
// two subarrays with equal product
static void prodEquilibrium(int arr[], int N)
{
     
    // Stores the product of the array
    int product = 1;
 
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
        product *= arr[i];
    }
 
    // Stores the product of left
    // and the right subarrays
    int left = 1;
    int right = product;
 
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // Update the products
        left = left * arr[i];
        right = right / arr[i];
 
        // Check if product is equal
        if (left == right)
        {
             
            // Print resultant index
            System.out.print(i + 1 + "\n");
            return;
        }
    }
 
    // If no partition exists, then
    // print -1.
    System.out.print(-1 + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 3, 2, 1 };
    int N = arr.length;
     
    prodEquilibrium(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 program for the above approach
 
# Function to find the smallest
# index that splits the array into
# two subarrays with equal product
def prodEquilibrium(arr, N):
   
    # Stores the product of the array
    product = 1
 
    # Traverse the given array
    for i in range(N):
        product *= arr[i]
 
    # Stores the product of left
    # and the right subarrays
    left = 1
    right = product
 
    # Traverse the given array
    for i in range(N):
        # Update the products
        left = left * arr[i]
        right = right // arr[i]
 
        # Check if product is equal
        if (left == right):
            # Print resultant index
            print(i + 1)
            return
 
    # If no partition exists, then
    # print -1.
    print(-1)
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 3, 2, 1]
    N = len(arr)
    prodEquilibrium(arr, N)
     
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
class GFG {
 
    // Function to find the smallest
    // index that splits the array into
    // two subarrays with equal product
    static void prodEquilibrium(int[] arr, int N)
    {
 
        // Stores the product of the array
        int product = 1;
 
        // Traverse the given array
        for (int i = 0; i < N; i++) {
            product *= arr[i];
        }
 
        // Stores the product of left
        // and the right subarrays
        int left = 1;
        int right = product;
 
        // Traverse the given array
        for (int i = 0; i < N; i++) {
 
            // Update the products
            left = left * arr[i];
            right = right / arr[i];
 
            // Check if product is equal
            if (left == right) {
 
                // Print resultant index
                Console.WriteLine(i + 1 + "\n");
                return;
            }
        }
 
        // If no partition exists, then
        // print -1.
        Console.WriteLine(-1 + "\n");
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 3, 2, 1 };
        int N = arr.Length;
 
        prodEquilibrium(arr, N);
    }
}
 
 // This code is contributed by ukasp.

<script>
// JavaScript program for the above approach
 
// Function to find the smallest
// index that splits the array into
// two subarrays with equal product
function prodEquilibrium(arr, N)
{
    // Stores the product of the array
    let product = 1;
 
    // Traverse the given array
    for (let i = 0; i < N; i++) {
        product *= arr[i];
    }
 
    // Stores the product of left
    // and the right subarrays
    let left = 1;
    let right = product;
 
    // Traverse the given array
    for (let i = 0; i < N; i++) {
 
        // Update the products
        left = left * arr[i];
        right = right / arr[i];
 
        // Check if product is equal
        if (left == right) {
 
            // Print resultant index
            document.write((i + 1) + "<br>");
            return;
        }
    }
 
    // If no partition exists, then
    // print -1.
    document.write((-1) + "<br>");
}
 
// Driver Code
 
    let arr = [ 1, 2, 3, 3, 2, 1 ];
    let N = arr.length;
    prodEquilibrium(arr, N);
     
    // This code is contributed by Dharanendra L V.
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)