Given an array arr[] of integers of size N, the task is to find the products of all subarrays of the array.
Examples:
Input: arr[] = {2, 4}
Output: 64
Explanation:
Here, subarrays are {2}, {2, 4}, and {4}.
Products of each subarray are 2, 8, 4.
Product of all Subarrays = 64
Input: arr[] = {1, 2, 3}
Output: 432
Explanation:
Here, subarrays are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, {3}.
Products of each subarray are 1, 2, 6, 2, 6, 3.
Product of all Subarrays = 432
Naive and Iterative approach: Please refer this post for these approaches.
Approach: The idea is to count the number of each element occurs in all the subarrays. To count we have below observations:
- In every subarray beginning with arr[i], there are (N – i) such subsets starting with the element arr[i].
For Example:
For array arr[] = {1, 2, 3}
N = 3 and for element 2 i.e., index = 1
There are (N – index) = 3 – 1 = 2 subsets
{2} and {2, 3}
- For any element arr[i], there are (N – i)*i subarrays where arr[i] is not the first element.
For array arr[] = {1, 2, 3}
N = 3 and for element 2 i.e., index = 1
There are (N – index)*index = (3 – 1)*1 = 2 subsets where 2 is not the first element.
{1, 2} and {1, 2, 3}
Therefore, from the above observations, the total number of each element arr[i] occurs in all the subarrays at every index i is given by:
total_elements = (N - i) + (N - i)*i total_elements = (N - i)*(i + 1)
The idea is to multiply each element (N – i)*(i + 1) number of times to get the product of elements in all subarrays.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the product of// elements of all subarraylong int SubArrayProdct(int arr[], int n){ // Initialize the result long int result = 1; // Computing the product of // subarray using formula for (int i = 0; i < n; i++) result *= pow(arr[i], (i + 1) * (n - i)); // Return the product of all // elements of each subarray return result;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 2, 4 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << SubArrayProdct(arr, N) << endl; return 0;} |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the product of// elements of all subarraystatic int SubArrayProdct(int arr[], int n){ // Initialize the result int result = 1; // Computing the product of // subarray using formula for(int i = 0; i < n; i++) result *= Math.pow(arr[i], (i + 1) * (n - i)); // Return the product of all // elements of each subarray return result;}// Driver code public static void main(String[] args) { // Given array arr[] int arr[] = new int[]{2, 4}; int N = arr.length; // Function Call System.out.println(SubArrayProdct(arr, N)); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach# Function to find the product of# elements of all subarraydef SubArrayProdct(arr, n): # Initialize the result result = 1; # Computing the product of # subarray using formula for i in range(0, n): result *= pow(arr[i], (i + 1) * (n - i)); # Return the product of all # elements of each subarray return result;# Driver Code# Given array arr[]arr = [ 2, 4 ];N = len(arr);# Function Callprint(SubArrayProdct(arr, N))# This code is contributed by Code_Mech |
C#
// C# program for the above approach using System;class GFG{ // Function to find the product of// elements of all subarraystatic int SubArrayProdct(int []arr, int n){ // Initialize the result int result = 1; // Computing the product of // subarray using formula for(int i = 0; i < n; i++) result *= (int)(Math.Pow(arr[i], (i + 1) * (n - i))); // Return the product of all // elements of each subarray return result;}// Driver code public static void Main() { // Given array arr[] int []arr = new int[]{2, 4}; int N = arr.Length; // Function Call Console.Write(SubArrayProdct(arr, N)); } } // This code is contributed by Code_Mech |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find the product of// elements of all subarrayfunction SubArrayProdct(arr, n){ // Initialize the result let result = 1; // Computing the product of // subarray using formula for(let i = 0; i < n; i++) result *= Math.pow(arr[i], (i + 1) * (n - i)); // Return the product of all // elements of each subarray return result;}// Driver code // Given array arr[] let arr = [2, 4]; let N = arr.length; // Function Call document.write(SubArrayProdct(arr, N)); // This code is contributed by sanjoy_62.</script> |
64
Time Complexity: O(N), where N is the number of elements.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!