Given, an array of size N. Find an element which divides the array into two sub-arrays with equal product. Print -1 if no such partition is not possible.
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}
A simple solution will be to consider every element starting from the second element. Compute the product of elements on its left and product of elements on its right. If these two products are same, return the element.
Time Complexity: O(N2)
A better solution will be to use prefix and suffix product arrays. Traverse from 0 to n-1th index, the index at which they yield an equal result, is the index where the array is partitioned with an equal product.
Time Complexity: O(N)
Auxiliary Space: O(N)
C++
#include <bits/stdc++.h>
using namespace std;
int findElement( int arr[], int n)
{
int prefixMul[n];
prefixMul[0] = arr[0];
for ( int i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] * arr[i];
int suffixMul[n];
suffixMul[n - 1] = arr[n - 1];
for ( int i = n - 2; i >= 0; i--)
suffixMul[i] = suffixMul[i + 1] * arr[i];
for ( int i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << findElement(arr, n);
return 0;
}
|
Java
class GFG
{
static int findElement( int arr[],
int n)
{
int prefixMul[] = new int [n];
prefixMul[ 0 ] = arr[ 0 ];
for ( int i = 1 ; i < n; i++)
prefixMul[i] = prefixMul[i - 1 ] *
arr[i];
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];
for ( int i = 1 ; i < n - 1 ; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return - 1 ;
}
public static void main(String args[])
{
int arr[] = { 2 , 3 , 4 ,
1 , 4 , 6 };
int n = arr.length;
System.out.println(findElement(arr, n));
}
}
|
Python3
def findElement(arr, n):
prefixMul = []
prefixMul.append(arr[ 0 ])
for i in range ( 1 , n):
prefixMul.append(prefixMul[i - 1 ] * arr[i])
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]
for i in range ( 1 , n - 1 ):
if prefixMul[i] = = suffixMul[i]:
return arr[i]
return - 1
arr = [ 2 , 3 , 4 , 1 , 4 , 6 ]
n = len (arr)
print (findElement(arr, n))
|
C#
using System;
class GFG
{
static int findElement( int []arr,
int n)
{
int []prefixMul = new int [n];
prefixMul[0] = arr[0];
for ( int i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] *
arr[i];
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];
for ( int i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
public static void Main()
{
int []arr = {2, 3, 4, 1, 4, 6};
int n = arr.Length;
Console.Write(findElement(arr, n));
}
}
|
PHP
<?php
function findElement( $arr , $n )
{
$prefixMul ;
$prefixMul [0] = $arr [0];
for ( $i = 1; $i < $n ; $i ++)
$prefixMul [ $i ] = $prefixMul [ $i - 1] *
$arr [ $i ];
$suffixMul ;
$suffixMul [ $n - 1] = $arr [ $n - 1];
for ( $i = $n - 2; $i >= 0; $i --)
$suffixMul [ $i ] = $suffixMul [ $i + 1] *
$arr [ $i ];
for ( $i = 1; $i < $n - 1; $i ++)
if ( $prefixMul [ $i ] == $suffixMul [ $i ])
return $arr [ $i ];
return -1;
}
$arr = array ( 2, 3, 4, 1, 4, 6 );
$n = sizeof( $arr ) / sizeof( $arr [0]);
echo findElement( $arr , $n );
?>
|
Javascript
<script>
function findElement(arr,n)
{
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];
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];
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));
</script>
|
C
#include <stdio.h>
int findElement( int arr[], int n)
{
int prefixMul[n];
prefixMul[0] = arr[0];
for ( int i = 1; i < n; i++)
prefixMul[i] = prefixMul[i - 1] * arr[i];
int suffixMul[n];
suffixMul[n - 1] = arr[n - 1];
for ( int i = n - 2; i >= 0; i--)
suffixMul[i] = suffixMul[i + 1] * arr[i];
for ( int i = 1; i < n - 1; i++)
if (prefixMul[i] == suffixMul[i])
return arr[i];
return -1;
}
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int n = sizeof (arr) / sizeof (arr[0]);
printf ( "%d" ,findElement(arr, n));
return 0;
}
|
An efficient solution will be to calculate the product of the whole array except the first element in right_mul, considering it to be the partitioning element. Now, we traverse the array from left to right, dividing an element from right_mul and multiplying an element to left_mul. The point where right_mul equals left_mul, we get the partition.
- Time Complexity: O(N)
- Auxiliary Space: O(1)
C++
#include <bits/stdc++.h>
using namespace std;
int findElement( int arr[], int size)
{
int right_mul = 1, left_mul = 1;
for ( int i = 1; i < size; i++)
right_mul *= arr[i];
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;
}
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int size = sizeof (arr) / sizeof (arr[0]);
cout << findElement(arr, size);
return 0;
}
|
C
#include <stdio.h>
int findElement( int arr[], int size)
{
int right_mul = 1, left_mul = 1;
for ( int i = 1; i < size; i++)
right_mul *= arr[i];
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;
}
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 6 };
int size = sizeof (arr) / sizeof (arr[0]);
printf ( "%d" ,findElement(arr, size));
return 0;
}
|
Java
class GFG
{
static int findElement( int arr[],
int size)
{
int right_mul = 1 ,
left_mul = 1 ;
for ( int i = 1 ; i < size; i++)
right_mul *= arr[i];
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 ;
}
public static void main(String args[])
{
int arr[] = { 2 , 3 , 4 , 1 , 4 , 6 };
int size = arr.length;
System.out.println(findElement(arr,
size));
}
}
|
Python3
def findElement(arr, size):
right_mul = 1 ;
left_mul = 1 ;
for i in range ( 1 ,size):
right_mul = right_mul * arr[i];
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 ;
arr = [ 2 , 3 , 4 , 1 , 4 , 6 ,];
size = len (arr) ;
print (findElement(arr, size));
|
C#
using System;
class GFG
{
static int findElement( int []arr,
int size)
{
int right_mul = 1,
left_mul = 1;
for ( int i = 1; i < size; i++)
right_mul *= arr[i];
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;
}
public static void Main()
{
int []arr = new int [] {2, 3, 4,
1, 4, 6};
int size = arr.Length;
Console.Write(findElement(arr, size));
}
}
|
PHP
<?php
function findElement( $arr , $size )
{
$right_mul = 1;
$left_mul = 1;
for ( $i = 1; $i < $size ; $i ++)
$right_mul *= $arr [ $i ];
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;
}
$arr = array (2, 3, 4, 1, 4, 6);
$size = sizeof( $arr ) /
sizeof( $arr [0]);
echo findElement( $arr , $size );
?>
|
Javascript
<script>
function findElement(arr , size) {
var right_mul = 1, left_mul = 1;
for (i = 1; i < size; i++)
right_mul *= arr[i];
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;
}
var arr = [ 2, 3, 4, 1, 4, 6 ];
var size = arr.length;
document.write(findElement(arr, size));
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us