Product of all Subarrays of an Array
Given an array of integers arr of size N, the task is to print products of all subarrays of the array.
Examples:
Input: arr[] = {2, 4}
Output: 64
Here, subarrays are [2], [2, 4], [4]
Products are 2, 8, 4
Product of all Subarrays = 64Input : arr[] = {10, 3, 7}
Output : 27783000
Here, subarrays are [10], [10, 3], [10, 3, 7], [3], [3, 7], [7]
Products are 10, 30, 210, 3, 21, 7
Product of all Subarrays = 27783000
Naive Approach: A simple solution is to generate all sub-array and compute their product.
C++
// C++ program to find product // of all subarray of an array #include <bits/stdc++.h> using namespace std; // Function to find product of all subarrays void product_subarrays( int arr[], int n) { // Variable to store the product int product = 1; // Compute the product while // traversing for subarrays for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { for ( int k = i; k <= j; k++) product *= arr[k]; } } // Printing product of all subarray cout << product << "\n" ; } // Driver code int main() { int arr[] = { 10, 3, 7 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call product_subarrays(arr, n); return 0; } |
Java
// Java program to find product // of all subarray of an array import java.util.*; class GFG { // Function to find product of all subarrays static void product_subarrays( int arr[], int n) { // Variable to store the product int product = 1 ; // Compute the product while // traversing for subarrays for ( int i = 0 ; i < n; i++) { for ( int j = i; j < n; j++) { for ( int k = i; k <= j; k++) product *= arr[k]; } } // Printing product of all subarray System.out.print(product + "\n" ); } // Driver code public static void main(String args[]) { int arr[] = { 10 , 3 , 7 }; int n = arr.length; // Function call product_subarrays(arr, n); } } // This code is contributed by shivanisinghss2110 |
Python3
# Python3 program to find product # of all subarray of an array # Function to find product of all subarrays def product_subarrays(arr, n): # Variable to store the product product = 1 ; # Compute the product while # traversing for subarrays for i in range ( 0 , n): for j in range (i, n): for k in range (i, j + 1 ): product * = arr[k]; # Printing product of all subarray print (product, "\n" ); # Driver code arr = [ 10 , 3 , 7 ]; n = len (arr); # Function call product_subarrays(arr, n); # This code is contributed by Code_Mech |
C#
// C# program to find product // of all subarray of an array using System; class GFG { // Function to find product of all subarrays static void product_subarrays( int [] arr, int n) { // Variable to store the product int product = 1; // Compute the product while // traversing for subarrays for ( int i = 0; i < n; i++) { for ( int j = i; j < n; j++) { for ( int k = i; k <= j; k++) product *= arr[k]; } } // Printing product of all subarray Console.Write(product + "\n" ); } // Driver code public static void Main(String[] args) { int [] arr = { 10, 3, 7 }; int n = arr.Length; // Function call product_subarrays(arr, n); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // Javascript program to find product // of all subarray of an array // Function to find product of all subarrays function product_subarrays(arr, n) { // Variable to store the product let product = 1; // Compute the product while // traversing for subarrays for (let i = 0; i < n; i++) { for (let j = i; j < n; j++) { for (let k = i; k <= j; k++) product *= arr[k]; } } // Printing product of all subarray document.write(product + "</br>" ); } let arr = [ 10, 3, 7 ]; let n = arr.length; // Function call product_subarrays(arr, n); // This code is contributed by divyeshrabadiya07. </script> |
27783000
Time Complexity: O(n3)
Auxiliary Space: O(1)
Efficient Approach: An efficient approach is to use two loops and calculate the products while traversing the subarrays.
Below is the implementation of the above approach:
C++
// C++ program to find product // of all subarray of an array #include <bits/stdc++.h> using namespace std; // Function to find product of all subarrays void product_subarrays( long long int arr[], int n) { // Variable to store the product long long int res = 1; // Compute the product while // traversing for subarrays for ( int i = 0; i < n; i++) { long long int product = 1; for ( int j = i; j < n; j++) { product = product * arr[j]; res *= product; } } // Printing product of all subarray cout << res << "\n" ; } // Driver code int main() { long long int arr[] = { 10, 3, 7 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call product_subarrays(arr, n); return 0; } |
Java
// Java program to find product // of all subarray of an array import java.util.*; class GFG { // Function to find product of all subarrays static void product_subarrays( int arr[], int n) { // Variable to store the product int res = 1 ; // Compute the product while // traversing for subarrays for ( int i = 0 ; i < n; i++) { int product = 1 ; for ( int j = i; j < n; j++) { product = product * arr[j]; res *= product; } } // Printing product of all subarray System.out.println(res + "\n" ); } // Driver code public static void main(String args[]) { int arr[] = { 10 , 3 , 7 }; int n = arr.length; // Function call product_subarrays(arr, n); } } // This code is contributed by AbhiThakur |
Python3
# Python3 program to find product # of all subarray of an array # Function to find product of all subarrays def product_subarrays(arr, n): # Variable to store the product res = 1 ; # Compute the product while # traversing for subarrays for i in range (n): product = 1 for j in range (i, n): product * = arr[j]; res = res * product # Printing product of all subarray print (res); # Driver code if __name__ = = '__main__' : arr = [ 10 , 3 , 7 ]; n = len (arr); # Function call product_subarrays(arr, n); # This code is contributed by Princi Singh |
C#
// C# program to find product // of all subarray of an array using System; class GFG { // Function to find product of all subarrays static void product_subarrays( int [] arr, int n) { // Variable to store the product int res = 1; // Compute the product while // traversing for subarrays for ( int i = 0; i < n; i++) { int product = 1; for ( int j = i; j < n; j++) { product *= arr[j]; res = res * product; } } // Printing product of all subarray Console.WriteLine(res + "\n" ); } // Driver code public static void Main(String[] args) { int [] arr = { 10, 3, 7 }; int n = arr.Length; // Function call product_subarrays(arr, n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find product // of all subarray of an array // Function to find product of all subarrays function product_subarrays(arr, n) { // Variable to store the product var res = 1; // Compute the product while // traversing for subarrays for ( var i = 0; i < n; i++) { var product = 1; for ( var j = i; j < n; j++) { product = product * arr[j]; res *= product; } } // Printing product of all subarray document.write( res ); } // Driver code var arr = [10, 3, 7]; var n = arr.length; // Function call product_subarrays(arr, n); </script> |
27783000
Time Complexity: O(n2)
Auxiliary Space: O(1)