Given an array arr[] of integers, the task is to find the number of indices for which the prefix product and the suffix product are equal.
Example:
Input: arr = [4, -5, 1, 1, -2, 5, -2]
Output: 2
Explanation: The indices on which the prefix and the suffix product are equal are given below:
At index 2 prefix and suffix product are 20
At index 3 prefix and suffix product are 20Input: arr = [5, 0, 4, -1, -3, 0]
Output: 3
Explanation: The indices on which the prefix and the suffix product are equal are given below:
At index 1 prefix and suffix product are 0
At index 2 prefix and suffix product are 0
At index 3 prefix and suffix product are 0
At index 4 prefix and suffix product are 0
At index 5 prefix and suffix product are 0
Naive Approach: The given problem can be solved by traversing the array arr from left to right and calculating prefix product till that index then iterating the array arr from right to left and calculating the suffix product then checking if prefix and suffix product are equal.
Time Complexity: O(N^2)
Better Approach:
This approach to solve the problem is to precompute and store prefix and suffix products in separate arrays. Traversing those arrays simultaneously and checking condition of equality will give our count of indices with equal prefix and suffix product.
Algorithm:
- Initialize a variable res to 0 to store the result.
- Initialize a vector arr to store the given input array.
- Initialize a variable n to store the length of the input array arr.
- Initialize two auxiliary arrays left_Product and right_Product of length n, to store prefix and suffix product at every index.
- Compute the prefix product of arr and store it in left_Product array using a for loop that iterates from 0 to n-1.
- Compute the suffix product of arr and store it in right_Product array using a for loop that iterates from n-2 to 0.
- Traverse the array arr using a for loop that iterates from 0 to n-1.
- For each element arr[i] in arr, if the prefix product left_Product[i] is equal to the suffix product right_Product[i], increment the result variable res by 1.
- Return the result variable res.
Below is the implementation of the approach:
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; // Length of array arr int n = arr.size(); // Initialize an auxiliary array to // store prefix and suffix product // at every index vector< int > left_Product(n); vector< int > right_Product(n); // store prefix product left_Product[0] = arr[0]; // Iterate the array from left to right for ( int i = 1; i < n; i++) { left_Product[i] = left_Product[i-1] * arr[i]; } // store suffix product right_Product[n-1] = arr[n-1]; // Traverse the array from right to left for ( int i=n - 2; i >= 0; i--) { right_Product[i] = right_Product[i+1] * arr[i]; } // Traverse the array for ( int i = 0; i < n; i++) { // If prefix product is equal to // suffix product prod[i] then // increment res by 1 if (left_Product[i] == right_Product[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; } |
Java
// Java implementation for the above approach import java.io.*; import java.util.*; public class GFG { // Function to calculate number of // equal prefix and suffix product // till the same indices public static int equalProdPreSuf(List<Integer> arr) { // Initialize a variable // to store the result int res = 0 ; // Length of array arr int n = arr.size(); // Initialize an auxiliary array to // store prefix and suffix product // at every index int [] left_Product = new int [n]; int [] right_Product = new int [n]; // store prefix product left_Product[ 0 ] = arr.get( 0 ); // Iterate the array from left to right for ( int i = 1 ; i < n; i++) { left_Product[i] = left_Product[i - 1 ] * arr.get(i); } // store suffix product right_Product[n - 1 ] = arr.get(n - 1 ); // Traverse the array from right to left for ( int i = n - 2 ; i >= 0 ; i--) { right_Product[i] = right_Product[i + 1 ] * arr.get(i); } // Traverse the array for ( int i = 0 ; i < n; i++) { // If prefix product is equal to // suffix product prod[i] then // increment res by 1 if (left_Product[i] == right_Product[i]) { // Increment the result res++; } } // Return the answer return res; } // Driver code public static void main(String[] args) { // Initialize the array List<Integer> arr = Arrays.asList( 4 , 5 , 1 , 1 , - 2 , 5 , - 2 ); // Call the function and // print its result System.out.println(equalProdPreSuf(arr)); } } // This code has been contributed by Pushpesh Raj |
Python3
# Function to calculate the number of equal prefix and suffix product # until the same indices def equal_prod_pre_suf(arr): # Initialize a variable to store the result res = 0 # Length of array 'arr' n = len (arr) # Initialize auxiliary arrays to store prefix and suffix products at every index left_product = [ 0 ] * n right_product = [ 0 ] * n # Calculate prefix products left_product[ 0 ] = arr[ 0 ] for i in range ( 1 , n): left_product[i] = left_product[i - 1 ] * arr[i] # Calculate suffix products right_product[n - 1 ] = arr[n - 1 ] for i in range (n - 2 , - 1 , - 1 ): right_product[i] = right_product[i + 1 ] * arr[i] # Traverse the array for i in range (n): # If prefix product is equal to suffix product at index 'i', increment 'res' by 1 if left_product[i] = = right_product[i]: res + = 1 # Return the result return res # Driver code if __name__ = = "__main__" : # Initialize the array arr = [ 4 , 5 , 1 , 1 , - 2 , 5 , - 2 ] # Call the function and print its result print (equal_prod_pre_suf(arr)) |
C#
using System; using System.Collections.Generic; class GFG { // Function to calculate the number of // equal prefix and suffix product public static int EqualProdPreSuf(List< int > arr) { // Initialize a variable // to store the result int res = 0; // Length of the array arr int n = arr.Count; // Initialize auxiliary arrays to // store prefix and suffix products int [] leftProduct = new int [n]; int [] rightProduct = new int [n]; // Calculate prefix product leftProduct[0] = arr[0]; for ( int i = 1; i < n; i++) { leftProduct[i] = leftProduct[i - 1] * arr[i]; } // Calculate suffix product rightProduct[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) { rightProduct[i] = rightProduct[i + 1] * arr[i]; } // Traverse the array for ( int i = 0; i < n; i++) { // If prefix product is equal to // suffix product, increment res by 1 if (leftProduct[i] == rightProduct[i]) { // Increment the result res++; } } // Return the answer return res; } // Driver code public static void Main( string [] args) { // Initialize the list List< int > arr = new List< int > { 4, 5, 1, 1, -2, 5, -2 }; // Call the function and // print its result Console.WriteLine(EqualProdPreSuf(arr)); } } |
Javascript
// Function to calculate the number of equal prefix and suffix products function equalProdPreSuf(arr) { // Initialize a variable to store the result let res = 0; // Length of the array 'arr' const n = arr.length; // Initialize auxiliary arrays to store prefix and suffix products at every index const leftProduct = new Array(n); const rightProduct = new Array(n); // Store prefix products leftProduct[0] = arr[0]; for (let i = 1; i < n; i++) { leftProduct[i] = leftProduct[i - 1] * arr[i]; } // Store suffix products rightProduct[n - 1] = arr[n - 1]; for (let i = n - 2; i >= 0; i--) { rightProduct[i] = rightProduct[i + 1] * arr[i]; } // Traverse the array for (let i = 0; i < n; i++) { // If the prefix product is equal to the suffix product at index 'i', increment 'res' if (leftProduct[i] === rightProduct[i]) { // Increment the result res++; } } // Return the answer return res; } // Driver code const arr = [4, 5, 1, 1, -2, 5, -2]; // Call the function and print its result console.log(equalProdPreSuf(arr)); |
2
Time Complexity : O(N), As we iterate the array (arr) thrice. Where N = size of the array.
Auxiliary Space : O(N), array left_Product and right_Product space. Where N = size of the array.
Efficient Approach: The above approach can be solved by using the Hashing technique. Follow the steps below to solve the problem:
- Traverse the array arr from right to left and at every index store the product into an auxiliary array prod
- Iterate the array arr from left to right and at every index calculate the prefix product
- For every prefix product obtained, check suffix product of the same value is present in prod
- If yes, then increment the count res by 1
- Return the result res obtained
Below is the implementation of the above approach:
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> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)