Dada, una array de tamaño N. Encuentre un elemento que divida la array en dos sub-arrays con el mismo producto. Imprima -1 si tal partición no es posible.
Ejemplos:
Input : 1 4 2 1 4
Output : 2
If 2 is the partition,
subarrays are : {1, 4} and {1, 4}
Input : 2, 3, 4, 1, 4, 6
Output : 1
If 1 is the partition,
Subarrays are : {2, 3, 4} and {4, 6}
Una solución simple será considerar cada elemento a partir del segundo elemento. Calcule el producto de los elementos a su izquierda y el producto de los elementos a su derecha. Si estos dos productos son iguales, devuelva el elemento.
Complejidad del Tiempo: O(N 2 )
Una mejor solución será utilizar arrays de productos de prefijos y sufijos. Traverse de 0 a n-1 th index, el índice en el que arrojan un resultado igual, es el índice donde la array se divide con un producto igual.
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
C++
// C++ program to find an element which divides
// the array in two sub-arrays with equal product.
#include <bits/stdc++.h>
using namespace std;
// Function to find the index
int findElement(int arr[], int n)
{
// Forming prefix sum array from 0
int prefixMul[n];
prefixMul[0] = arr[0];
for (int i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] * arr[i];
// Forming suffix sum array from n-1
int suffixMul[n];
suffixMul[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffixMul[i] = suffixMul[i + 1] * arr[i];
// Find the point where prefix and suffix
// sums are same.
for (int i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findElement(arr, n);
return 0;
}
Java
// Java program to find an element
// which divides the array in two
// sub-arrays with equal product.
class GFG
{
// Function to find
// the index
static int findElement(int arr[],
int n)
{
// Forming prefix
// sum array from 0
int prefixMul[] = new int[n];
prefixMul[0] = arr[0];
for (int i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] *
arr[i];
// Forming suffix sum
// array from n-1
int suffixMul[] = new int[n];
suffixMul[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffixMul[i] = suffixMul[i + 1] *
arr[i];
// Find the point where prefix
// and suffix sums are same.
for (int i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = {2, 3, 4,
1, 4, 6};
int n = arr.length;
System.out.println(findElement(arr, n));
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 program to find an element # which divides the array in two # sub-arrays with equal product. # Function to find the index def findElement(arr, n): # Forming prefix sum array from 0 prefixMul = [] prefixMul.append(arr[0]) for i in range(1, n): prefixMul.append(prefixMul[i-1]*arr[i]) # Forming suffix sum array from n-1 suffixMul = [None for i in range(0, n)] suffixMul[n-1] = arr[n-1] for i in range(n-2, -1, -1): suffixMul[i] = suffixMul[i+1]*arr[i] # Find the point where prefix and suffix # sums are same. for i in range(1, n-1): if prefixMul[i] == suffixMul[i]: return arr[i] return -1 # Driver Code arr = [2, 3, 4, 1, 4, 6] n = len(arr) print(findElement(arr, n)) # This code is contributed by SamyuktaSHegde
C#
// C# program to find an element
// which divides the array in two
// sub-arrays with equal product.
using System;
class GFG
{
// Function to find
// the index
static int findElement(int []arr,
int n)
{
// Forming prefix
// sum array from 0
int []prefixMul = new int[n];
prefixMul[0] = arr[0];
for (int i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] *
arr[i];
// Forming suffix sum
// array from n-1
int []suffixMul = new int[n];
suffixMul[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffixMul[i] = suffixMul[i + 1] *
arr[i];
// Find the point where prefix
// and suffix sums are same.
for (int i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
// Driver code
public static void Main()
{
int []arr = {2, 3, 4, 1, 4, 6};
int n = arr.Length;
Console.Write(findElement(arr, n));
}
}
// This code is contributed
// by shiv_bhakt
PHP
<?php
// PHP program to find an
// element which divides
// the array in two sub-
// arrays with equal product.
// Function to find the index
function findElement($arr, $n)
{
// Forming prefix
// sum array from 0
$prefixMul;
$prefixMul[0] = $arr[0];
for ($i = 1; $i < $n; $i++)
$prefixMul[$i] = $prefixMul[$i - 1] *
$arr[$i];
// Forming suffix
// sum array from n-1
$suffixMul;
$suffixMul[$n - 1] = $arr[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
$suffixMul[$i] = $suffixMul[$i + 1] *
$arr[$i];
// Find the point where
// prefix and suffix sums
// are same.
for ($i = 1; $i < $n - 1; $i++)
if ($prefixMul[$i] == $suffixMul[$i])
return $arr[$i];
return -1;
}
// Driver code
$arr = array( 2, 3, 4, 1, 4, 6 );
$n = sizeof($arr) / sizeof($arr[0]);
echo findElement($arr, $n);
// This code is contributed
// by shiv_bhakt
?>
Javascript
<script>
// javascript program to find an element which divides
// the array in two sub-arrays with equal product.
// Function to find the index
function findElement(arr,n)
{
// Forming prefix sum array from 0
let prefixMul= new Array(n);
prefixMul.fill(0);
prefixMul[0] = arr[0];
for (let i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] * arr[i];
// Forming suffix sum array from n-1
let suffixMul=new Array(n);
suffixMul.fill(0);
suffixMul[0] = arr[0];
suffixMul[n - 1] = arr[n - 1];
for (let i = n - 2; i >= 0; i--)
suffixMul[i] = suffixMul[i + 1] * arr[i];
// Find the point where prefix and suffix
// sums are same.
for (let i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
let arr = [2, 3, 4, 1, 4, 6 ];
let n = arr.length;
document.write(findElement(arr, n));
// This code is contributed by vaibhavrabadiya117.
</script>
C
// C program to find an element which divides
// the array in two sub-arrays with equal product.
#include <stdio.h>
// Function to find the index
int findElement(int arr[], int n)
{
// Forming prefix sum array from 0
int prefixMul[n];
prefixMul[0] = arr[0];
for (int i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] * arr[i];
// Forming suffix sum array from n-1
int suffixMul[n];
suffixMul[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffixMul[i] = suffixMul[i + 1] * arr[i];
// Find the point where prefix and suffix
// sums are same.
for (int i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d",findElement(arr, n));
return 0;
}
Producción:
1
Una solución eficiente será calcular el producto de todo el arreglo excepto el primer elemento en right_mul, considerándolo como el elemento de partición. Ahora, recorremos la array de izquierda a derecha, dividiendo un elemento de right_mul y multiplicando un elemento por left_mul. El punto donde right_mul es igual a left_mul, obtenemos la partición.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
C++
// C++ program to find an element which divides
// the array in two sub-arrays with equal product.
#include <bits/stdc++.h>
using namespace std;
// Function to compute partition
int findElement(int arr[], int size)
{
int right_mul = 1, left_mul = 1;
// Computing right_sum
for (int i = 1; i < size; i++)
right_mul *= arr[i];
// Checking the point of partition
// i.e. left_Sum == right_sum
for (int i = 0, j = 1; j < size; i++, j++) {
right_mul /= arr[j];
left_mul *= arr[i];
if (left_mul == right_mul)
return arr[i + 1];
}
return -1;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << findElement(arr, size);
return 0;
}
C
// C program to find an element which divides
// the array in two sub-arrays with equal product.
#include <stdio.h>
// Function to compute partition
int findElement(int arr[], int size)
{
int right_mul = 1, left_mul = 1;
// Computing right_sum
for (int i = 1; i < size; i++)
right_mul *= arr[i];
// Checking the point of partition
// i.e. left_Sum == right_sum
for (int i = 0, j = 1; j < size; i++, j++) {
right_mul /= arr[j];
left_mul *= arr[i];
if (left_mul == right_mul)
return arr[i + 1];
}
return -1;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int size = sizeof(arr) / sizeof(arr[0]);
printf("%d",findElement(arr, size));
return 0;
}
// This code is contributed by kothavvsaakash
Java
// Java program to find an
// element which divides the
// array in two sub-arrays
// with equal product.
class GFG
{
// Function to
// compute partition
static int findElement(int arr[],
int size)
{
int right_mul = 1,
left_mul = 1;
// Computing right_sum
for (int i = 1; i < size; i++)
right_mul *= arr[i];
// Checking the point of
// partition i.e. left_Sum
// == right_sum
for (int i = 0, j = 1;
j < size; i++, j++)
{
right_mul /= arr[j];
left_mul *= arr[i];
if (left_mul == right_mul)
return arr[i + 1];
}
return -1;
}
// Driver Code
public static void main(String args[])
{
int arr[] = {2, 3, 4, 1, 4, 6};
int size = arr.length;
System.out.println(findElement(arr,
size));
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python program to find an element which divides # the array in two sub-arrays with equal product. # Function to compute partition def findElement(arr, size): right_mul = 1; left_mul = 1; # Computing right_sum for i in range(1,size): right_mul = right_mul *arr[i]; # Checking the point of partition # i.e. left_Sum == right_sum for i, j in zip(range(0,size), range(1, size, 1)): right_mul =right_mul / arr[j]; left_mul = left_mul * arr[i]; if (left_mul == right_mul): return arr[i + 1]; return -1; # Driver Code arr = [ 2, 3, 4, 1, 4, 6,]; size = len(arr) ; print(findElement(arr, size)); #This code is contributed by Shivi_Aggarwal
C#
// C# program to find an
// element which divides the
// array in two sub-arrays
// with equal product.
using System;
class GFG
{
// Function to
// compute partition
static int findElement(int []arr,
int size)
{
int right_mul = 1,
left_mul = 1;
// Computing right_sum
for (int i = 1; i < size; i++)
right_mul *= arr[i];
// Checking the point of
// partition i.e. left_Sum
// == right_sum
for (int i = 0, j = 1;
j < size; i++, j++)
{
right_mul /= arr[j];
left_mul *= arr[i];
if (left_mul == right_mul)
return arr[i + 1];
}
return -1;
}
// Driver Code
public static void Main()
{
int []arr = new int[] {2, 3, 4,
1, 4, 6};
int size = arr.Length;
Console.Write(findElement(arr, size));
}
}
// This code is contributed
// by shiv_bhakt.
PHP
<?php
// PHP program to find an
// element which divides
// the array in two sub-
// arrays with equal product.
// Function to compute partition
function findElement($arr, $size)
{
$right_mul = 1;
$left_mul = 1;
// Computing right_sum
for ($i = 1; $i < $size; $i++)
$right_mul *= $arr[$i];
// Checking the point
// of partition i.e.
// left_Sum == right_sum
for ($i = 0, $j = 1;
$j < $size; $i++, $j++)
{
$right_mul /= $arr[$j];
$left_mul *= $arr[$i];
if ($left_mul == $right_mul)
return $arr[$i + 1];
}
return -1;
}
// Driver Code
$arr = array(2, 3, 4, 1, 4, 6);
$size = sizeof($arr) /
sizeof($arr[0]);
echo findElement($arr, $size);
// This code is contributed
// by shiv_bhakt.
?>
Javascript
<script>
// javascript program to find an
// element which divides the
// array in two sub-arrays
// with equal product. // Function to
// compute partition
function findElement(arr , size) {
var right_mul = 1, left_mul = 1;
// Computing right_sum
for (i = 1; i < size; i++)
right_mul *= arr[i];
// Checking the point of
// partition i.e. left_Sum
// == right_sum
for (i = 0, j = 1; j < size; i++, j++) {
right_mul /= arr[j];
left_mul *= arr[i];
if (left_mul == right_mul)
return arr[i + 1];
}
return -1;
}
// Driver Code
var arr = [ 2, 3, 4, 1, 4, 6 ];
var size = arr.length;
document.write(findElement(arr, size));
// This code contributed by umadevi9616
</script>
Producción :
1
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA