Given an array containing distinct integers arr[] of size N, the task is to print the product of all non-repeating subarrays of the array.
Examples:
Input: arr[] = {2, 4}
Output: 64
Explanation:
The possible subarrays for the given array are {2}, {2, 4}, {4}
The products are 2, 8, 4 respectively. Therefore, the overall product of all the subarrays = 64
Input: arr[] = {10, 3, 7}
Output: 1944810000
Explanation:
The possible subarrays for the given array are {10}, {10, 3}, {0, 7}, {10, 3, 7}, {3}, {7}, {3, 7}.
The products are 10, 30, 70, 210, 3, 7, 21 respectively. Therefore, the overall product of all the subarrays = 1944810000
Naive Approach: The naive approach for this problem is to generate all the sub-arrays of the given array and compute their product. The time complexity of this approach is exponential.
Efficient Approach: The idea is to make an observation. If we observe the non-repeating sub-arrays, we can observe that the occurrences of a single element in the sub-arrays follows a relationship with the length of the array.
- For example, let the array arr[] = {10, 3, 7}.
- All the non repeating possible subarrays of the above array are: {{10}, {10, 3}, {10, 7}, {10, 3, 7}, {3}, {7}, {3, 7}}.
- In the above sub-arrays, the frequency of every element can be observed as:
Frequency of 10 in subarrays = 4 Frequency of 3 in subarrays = 4 Frequency of 7 in subarrays = 4
- Here, the following identity holds true for the arrays of any length:
Frequency of element = 2(arr.length-1)
- Hence, in order to get the final product, we can simply perform:
product = 10 * (freq_of_10) * 3 * (freq_of_3) * 7 * (freq_of_7)
- Therefore, the idea is to simply iterate through the array and perform multiplication of every element and its corresponding frequency.
Below is the implementation of the above approach:
C++
// C++ program to find the product of// all non-repeating Subarrays of an Array#include <bits/stdc++.h>using namespace std;// Function to find the product of// all non-repeating Subarrays of an Arraylong product(int arr[], int n){ // Finding the occurrence of every element double occurrence = pow(2, n - 1); double product = 1; // Iterating through the array and // finding the product for(int i = 0; i < n; i++) { // We are taking the power of each // element in array with the occurrence // and then taking product of those. product *= pow(arr[i], occurrence); } return (long)product;}// Driver codeint main() { int arr[] = { 10, 3, 7 }; int len = sizeof(arr) / sizeof(arr[0]); cout << product(arr, len); return 0;}// This code is contributed by PrinciRaj1992 |
Java
// Java program to find the product of// all non-repeating Subarrays of an Arraypublic class GFG { // Function to find the product of // all non-repeating Subarrays of an Array private static long product(int[] arr) { // Finding the occurrence of every element double occurrence = Math.pow(2, arr.length - 1); double product = 1; // Iterating through the array and // finding the product for (int i = 0; i < arr.length; i++) { // We are taking the power of each // element in array with the occurrence // and then taking product of those. product *= Math.pow(arr[i], occurrence); } return (long)product; } // Driver code public static void main(String[] args) { int[] arr = { 10, 3, 7 }; System.out.println(product(arr)); }} |
Python3
# Python3 program to find the product of# all non-repeating Subarrays of an Array# Function to find the product of# all non-repeating Subarrays of an Arraydef product(arr): # Finding the occurrence of every element occurrence = pow(2, len(arr) - 1); product = 1; # Iterating through the array and # finding the product for i in range(0, len(arr)): # We are taking the power of each # element in array with the occurrence # and then taking product of those. product *= pow(arr[i], occurrence); return product;# Driver codearr = [ 10, 3, 7 ];print(product(arr));# This code is contributed by Code_Mech |
C#
// C# program to find the product of// all non-repeating Subarrays of an Arrayusing System;class GFG{// Function to find the product of// all non-repeating Subarrays of an Arrayprivate static long product(int[] arr){ // Finding the occurrence of every element double occurrence = Math.Pow(2, arr.Length - 1); double product = 1; // Iterating through the array and // finding the product for (int i = 0; i < arr.Length; i++) { // We are taking the power of each // element in array with the occurrence // and then taking product of those. product *= Math.Pow(arr[i], occurrence); } return (long)product;}// Driver codepublic static void Main(String[] args){ int[] arr = { 10, 3, 7 }; Console.WriteLine(product(arr));}}// This code is contributed by amal kumar choubey |
Javascript
<script>// Javascript program to find the product of// all non-repeating Subarrays of an Array // Function to find the product of // all non-repeating Subarrays of an Array function product(arr) { // Finding the occurrence of every element let occurrence = Math.pow(2, arr.length - 1); let product = 1; // Iterating through the array and // finding the product for (let i = 0; i < arr.length; i++) { // We are taking the power of each // element in array with the occurrence // and then taking product of those. product *= Math.pow(arr[i], occurrence); } return product; }// Driver Code let arr = [ 10, 3, 7 ]; document.write(product(arr)); </script> |
1944810000
Time Complexity: O(N), where N is the size of the array
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
