Dada una array arr[] de enteros, la tarea es encontrar el número de índices para los cuales el producto del prefijo y el producto del sufijo son iguales.
Ejemplo:
Entrada: arr= [4, -5, 1, 1, -2, 5, -2]
Salida: 2
Explicación: Los índices en los que el prefijo y el sufijo son iguales son los siguientes:
En el índice 2 prefijo y sufijo producto son 20
En el índice 3 el prefijo y el sufijo son 20Entrada: arr = [5, 0, 4, -1, -3, 0]
Salida: 3
Explicación: Los índices en los que el prefijo y el sufijo son iguales son los siguientes:
En el índice 1, el prefijo y el sufijo son 0
En el producto de prefijo y sufijo de índice 2 es 0 En el producto
de prefijo y sufijo de índice 3 son 0 En el producto de prefijo y sufijo
de índice 4 son 0
En el producto de prefijo y sufijo de índice 5 son 0
Enfoque ingenuo: el problema dado se puede resolver recorriendo la array arr de izquierda a derecha y calculando el producto del prefijo hasta ese índice, luego iterando la array arr de derecha a izquierda y calculando el producto del sufijo y luego verificando si el prefijo y el producto del sufijo son iguales.
Complejidad del tiempo: O(N^2)
Enfoque eficiente: el enfoque anterior se puede resolver utilizando Hashing . Siga los pasos a continuación para resolver el problema:
- Atraviese la array arr de derecha a izquierda y en cada índice almacene el producto en una array auxiliar prod
- Itere la array arr de izquierda a derecha y en cada índice calcule el producto del prefijo
- Para cada producto de prefijo obtenido, verifique que el producto de sufijo del mismo valor esté presente en prod
- En caso afirmativo, incremente el conteo res en 1
- Devolver el resultado res obtenido
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate number of
// equal prefix and suffix product
// till the same indices
int equalProdPreSuf(vector<int>& arr)
{
// Initialize a variable
// to store the result
int res = 0;
// Initialize variables to
// calculate prefix and suffix sums
int preProd = 1, sufProd = 1;
// Length of array arr
int len = arr.size();
// Initialize an auxiliary array to
// store suffix product at every index
vector<int> prod(len, 0);
// Traverse the array from right to left
for (int i = len - 1; i >= 0; i--) {
// Multiply the current
// element to sufSum
sufProd *= arr[i];
// Store the value in prod
prod[i] = sufProd;
}
// Iterate the array from left to right
for (int i = 0; i < len; i++) {
// Multiply the current
// element to preProd
preProd *= arr[i];
// If prefix product is equal to
// suffix product prod[i] then
// increment res by 1
if (preProd == prod[i]) {
// Increment the result
res++;
}
}
// Return the answer
return res;
}
// Driver code
int main()
{
// Initialize the array
vector<int> arr = { 4, 5, 1, 1, -2, 5, -2 };
// Call the function and
// print its result
cout << equalProdPreSuf(arr);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to calculate number of
// equal prefix and suffix product
// till the same indices
public static int equalProdPreSuf(int[] arr)
{
// Initialize a variable
// to store the result
int res = 0;
// Initialize variables to
// calculate prefix and suffix sums
int preProd = 1, sufProd = 1;
// Length of array arr
int len = arr.length;
// Initialize an auxiliary array to
// store suffix product at every index
int[] prod = new int[len];
// Traverse the array from right to left
for (int i = len - 1; i >= 0; i--) {
// Multiply the current
// element to sufSum
sufProd *= arr[i];
// Store the value in prod
prod[i] = sufProd;
}
// Iterate the array from left to right
for (int i = 0; i < len; i++) {
// Multiply the current
// element to preProd
preProd *= arr[i];
// If prefix product is equal to
// suffix product prod[i] then
// increment res by 1
if (preProd == prod[i]) {
// Increment the result
res++;
}
}
// Return the answer
return res;
}
// Driver code
public static void main(String[] args)
{
// Initialize the array
int[] arr = { 4, 5, 1, 1, -2, 5, -2 };
// Call the function and
// print its result
System.out.println(equalProdPreSuf(arr));
}
}
Python3
# Python Program to implement # the above approach # Function to calculate number of # equal prefix and suffix product # till the same indices def equalProdPreSuf(arr): # Initialize a variable # to store the result res = 0 # Initialize variables to # calculate prefix and suffix sums preProd = 1 sufProd = 1 # Length of array arr Len = len(arr) # Initialize an auxiliary array to # store suffix product at every index prod = [0] * Len # Traverse the array from right to left for i in range(Len-1, 0, -1): # Multiply the current # element to sufSum sufProd *= arr[i] # Store the value in prod prod[i] = sufProd # Iterate the array from left to right for i in range(Len): # Multiply the current # element to preProd preProd *= arr[i] # If prefix product is equal to # suffix product prod[i] then # increment res by 1 if (preProd == prod[i]): # Increment the result res += 1 # Return the answer return res # Driver code # Initialize the array arr = [4, 5, 1, 1, -2, 5, -2] # Call the function and # print its result print(equalProdPreSuf(arr)) # This code is contributed by gfgking.
C#
// C# implementation for the above approach
using System;
class GFG {
// Function to calculate number of
// equal prefix and suffix product
// till the same indices
public static int equalProdPreSuf(int[] arr)
{
// Initialize a variable
// to store the result
int res = 0;
// Initialize variables to
// calculate prefix and suffix sums
int preProd = 1, sufProd = 1;
// Length of array arr
int len = arr.Length;
// Initialize an auxiliary array to
// store suffix product at every index
int[] prod = new int[len];
// Traverse the array from right to left
for (int i = len - 1; i >= 0; i--) {
// Multiply the current
// element to sufSum
sufProd *= arr[i];
// Store the value in prod
prod[i] = sufProd;
}
// Iterate the array from left to right
for (int i = 0; i < len; i++) {
// Multiply the current
// element to preProd
preProd *= arr[i];
// If prefix product is equal to
// suffix product prod[i] then
// increment res by 1
if (preProd == prod[i]) {
// Increment the result
res++;
}
}
// Return the answer
return res;
}
// Driver code
public static void Main(String[] args)
{
// Initialize the array
int[] arr = { 4, 5, 1, 1, -2, 5, -2 };
// Call the function and
// print its result
Console.Write(equalProdPreSuf(arr));
}
}
// This code is contributed by gfgking.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to calculate number of
// equal prefix and suffix product
// till the same indices
function equalProdPreSuf(arr) {
// Initialize a variable
// to store the result
let res = 0;
// Initialize variables to
// calculate prefix and suffix sums
let preProd = 1, sufProd = 1;
// Length of array arr
let len = arr.length;
// Initialize an auxiliary array to
// store suffix product at every index
let prod = new Array(len).fill(0);
// Traverse the array from right to left
for (let i = len - 1; i >= 0; i--) {
// Multiply the current
// element to sufSum
sufProd *= arr[i];
// Store the value in prod
prod[i] = sufProd;
}
// Iterate the array from left to right
for (let i = 0; i < len; i++) {
// Multiply the current
// element to preProd
preProd *= arr[i];
// If prefix product is equal to
// suffix product prod[i] then
// increment res by 1
if (preProd == prod[i]) {
// Increment the result
res++;
}
}
// Return the answer
return res;
}
// Driver code
// Initialize the array
let arr = [4, 5, 1, 1, -2, 5, -2];
// Call the function and
// print its result
document.write(equalProdPreSuf(arr));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)