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++
// 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
// 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
Python3
# 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#
// 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.
Javascript
<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>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vikrantv45 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA