Given an array arr[], the task is to print all possible subarrays having a product of its elements less than or equal to K.
Input: arr[] = {2, 1, 3, 4, 5, 6, 2}, K = 10
Output: [[2], [1], [2, 1], [3], [1, 3], [2, 1, 3], [4], [5], [6], [2]]
Explanation:
All possible subarrays having product ? K are {2}, {1}, {2, 1}, {3}, {1, 3}, {2, 1, 3}, {4}, {5}, {6}, {2}.Input: arr[] = {2, 7, 1, 4}, K = 7
Output: [[2], [7], [1], [7, 1], [4], [1, 4]]
Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays from the given array and for each subarray, check if its product is less than or equal to K or not and print accordingly.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to return all possible// subarrays having product less// than or equal to Kvector<vector<int> > maxSubArray(int arr[], int n, int K){ vector<vector<int> > result; for (int i = 0; i < n; i++) { vector<int> res; long long product = 1; for (int j = i; j < n; j++) { product *= arr[j]; res.push_back(arr[j]); if (product <= K) { result.push_back(res); } } } return result;}// Driver Codeint main(){ int arr[] = { 2, 7, 1, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 7; vector<vector<int> > v = maxSubArray(arr, n, K); cout << "["; bool first = true; for (auto x : v) { if (!first) { cout << ", "; } else { first = false; } cout << "["; bool ff = true; for (int y : x) { if (!ff) { cout << ", "; } else { ff = false; } cout << y; } cout << "]"; } cout << "]"; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Gfg { // Function to return all possible // subarrays having product less // than or equal to K static List<List<Integer>> maxSubArray(int[] arr, int n, int K) { List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < n; i++) { List<Integer> res = new ArrayList<>(); long product = 1; for (int j = i; j < n; j++) { product *= arr[j]; res.add(arr[j]); if (product <= K) { result.add(new ArrayList<>(res)); } } } return result; } public static void main(String[] args) { int[] arr = { 2, 7, 1, 4 }; int n = arr.length; int K = 7; List<List<Integer>> v = maxSubArray(arr, n, K); System.out.print("["); boolean first = true; for (List<Integer> x : v) { if (!first) { System.out.print(", "); } else { first = false; } System.out.print("["); boolean ff = true; for (int y : x) { if (!ff) { System.out.print(", "); } else { ff = false; } System.out.print(y); } System.out.print("]"); } System.out.print("]"); }} |
C#
using System;using System.Collections.Generic;class Gfg { // Function to return all possible // subarrays having product less // than or equal to K static List<List<int> > maxSubArray(int[] arr, int n, int K) { List<List<int> > result = new List<List<int> >(); for (int i = 0; i < n; i++) { List<int> res = new List<int>(); long product = 1; for (int j = i; j < n; j++) { product *= arr[j]; res.Add(arr[j]); if (product <= K) { result.Add(new List<int>(res)); } } } return result; } public static void Main() { int[] arr = { 2, 7, 1, 4 }; int n = arr.Length; int K = 7; List<List<int> > v = maxSubArray(arr, n, K); Console.Write("["); bool first = true; foreach(List<int> x in v) { if (!first) { Console.Write(", "); } else { first = false; } Console.Write("["); bool ff = true; foreach(int y in x) { if (!ff) { Console.Write(", "); } else { ff = false; } Console.Write(y); } Console.Write("]"); } Console.Write("]"); }} |
Python3
from typing import Listdef max_sub_array(arr: List[int], n: int, K: int) -> List[List[int]]: # Create an empty list to hold the result result = [] # Loop through all possible subarrays of arr for i in range(n): # Create a new list to hold the current # subarray res = [] # Initialize a variable to hold the product # of the current subarray product = 1 # Loop through the elements of the current # subarray for j in range(i, n): # Multiply the current element with the # running product product *= arr[j] # Add the current element to the current # subarray res.append(arr[j]) # If the product of the current subarray # is less than or equal to K, # add the current subarray to the result list if product <= K: # We need to make a copy of the list # here because lists are mutable in Python result.append(res.copy()) return resultif __name__ == '__main__': arr = [2, 7, 1, 4] n = len(arr) K = 7 v = max_sub_array(arr, n, K) # Print the result in the specified format print("[", end="") first = True for x in v: if not first: print(", ", end="") else: first = False print("[", end="") ff = True for y in x: if not ff: print(", ", end="") else: ff = False print(y, end="") print("]", end="") print("]") |
Javascript
// javascript program to implement// the above approach// Function to return all possible// subarrays having product less// than or equal to Kfunction maxSubArray(arr, n, K){ let result = []; for (let i = 0; i < n; i++) { let res = new Array(); let product = 1; for (let j = i; j < n; j++) { product *= arr[j]; res.push(arr[j]); if (product <= K) { console.log(res); result.push(res); } } } return result;}// Driver Codelet arr = [ 2, 7, 1, 4 ];let n = arr.length;let K = 7;let v = maxSubArray(arr, n, K);// The code is contributed by Arushi Jindal. |
Output
[[2], [7], [7, 1], [1], [1, 4], [4]]
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient Approach: The above approach can be optimized by observing that:
If the product of all the elements of a subarray is less than or equal to K, then all the subarrays possible from this subarray also has product less than or equal to K. Therefore, these subarrays need to be included in the answer as well.
Follow the steps below to solve the problem:
- Initialize a pointer start pointing to the first index of the array.
- Iterate over the array and keep calculating the product of the array elements and store it in a variable, say multi.
- If multi exceeds K: keep dividing multi by arr[start] and keep incrementing start until multi reduces to ? K.
- If multi ? K: Iterate from the current index to start, and store the subarrays in an Arraylist.
- Finally, once all subarrays are generated, print the Arraylist which contains all the subarrays obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include<bits/stdc++.h>using namespace std;// Function to return all possible// subarrays having product less// than or equal to Kvector<vector<int>> maxSubArray(int arr[], int n, int K){ // Store the required subarrays vector<vector<int>> solution; // Stores the product of // current subarray int multi = 1; // Stores the starting index // of the current subarray int start = 0; // Check for empty array if (n <= 1 || K < 0) { return solution; } // Iterate over the array for(int i = 0; i < n; i++) { // Calculate product multi = multi * arr[i]; // If product exceeds K while (multi > K) { // Reduce product multi = multi / arr[start]; // Increase starting index // of current subarray start++; } // Stores the subarray elements vector<int> list; // Store the subarray elements for(int j = i; j >= start; j--) { list.insert(list.begin(), arr[j]); // Add the subarrays // to the list solution.push_back(list); } } // Return the final // list of subarrays return solution;}// Driver Codeint main(){ int arr[] = { 2, 7, 1, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 7; vector<vector<int>> v = maxSubArray(arr, n, K); cout << "["; bool first = true; for(auto x : v) { if (!first) { cout << ", "; } else { first = false; } cout << "["; bool ff = true; for(int y : x) { if (!ff) { cout << ", "; } else { ff = false; } cout << y; } cout << "]"; } cout << "]"; return 0;}// This code is contributed by rutvik_56 |
Java
// Java Program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to return all possible // subarrays having product less // than or equal to K public static List<List<Integer> > maxSubArray( int[] arr, int K) { // Store the required subarrays List<List<Integer> > solution = new ArrayList<>(); // Stores the product of // current subarray int multi = 1; // Stores the starting index // of the current subarray int start = 0; // Check for empty array if (arr.length <= 1 || K < 0) { return new ArrayList<>(); } // Iterate over the array for (int i = 0; i < arr.length; i++) { // Calculate product multi = multi * arr[i]; // If product exceeds K while (multi > K) { // Reduce product multi = multi / arr[start]; // Increase starting index // of current subarray start++; } // Stores the subarray elements List<Integer> list = new ArrayList<>(); // Store the subarray elements for (int j = i; j >= start; j--) { list.add(0, arr[j]); // Add the subarrays // to the list solution.add( new ArrayList<>(list)); } } // Return the final // list of subarrays return solution; } // Driver Code public static void main(String[] args) { int[] arr = { 2, 7, 1, 4 }; int K = 7; System.out.println(maxSubArray(arr, K)); }} |
Python3
# Python3 program to implement# the above approach # Function to return all possible# subarrays having product less# than or equal to Kdef maxSubArray(arr, n, K): # Store the required subarrays solution = [] # Stores the product of # current subarray multi = 1 # Stores the starting index # of the current subarray start = 0 # Check for empty array if (n <= 1 or K < 0): return solution # Iterate over the array for i in range(n): # Calculate product multi = multi * arr[i] # If product exceeds K while (multi > K): # Reduce product multi = multi // arr[start] # Increase starting index # of current subarray start += 1 # Stores the subarray elements li = [] j = i # Store the subarray elements while(j >= start): li.insert(0, arr[j]) # Add the subarrays # to the li solution.append(list(li)) j -= 1 # Return the final # li of subarrays return solution # Driver Codeif __name__=='__main__': arr = [ 2, 7, 1, 4 ] n = len(arr) K = 7 v = maxSubArray(arr, n, K) print(v) # This code is contributed by pratham76 |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to return all possible// subarrays having product less// than or equal to Kpublic static List<List<int>> maxSubArray(int[] arr, int K){ // Store the required subarrays List<List<int> > solution = new List<List<int>>(); // Stores the product of // current subarray int multi = 1; // Stores the starting index // of the current subarray int start = 0; // Check for empty array if (arr.Length <= 1 || K < 0) { return new List<List<int>>(); } // Iterate over the array for (int i = 0; i < arr.Length; i++) { // Calculate product multi = multi * arr[i]; // If product exceeds K while (multi > K) { // Reduce product multi = multi / arr[start]; // Increase starting index // of current subarray start++; } // Stores the subarray elements List<int> list = new List<int>(); // Store the subarray elements for (int j = i; j >= start; j--) { list.Insert(0, arr[j]); // Add the subarrays // to the list solution.Add(new List<int>(list)); } } // Return the final // list of subarrays return solution;}// Driver Codepublic static void Main(String[] args){ int[] arr = {2, 7, 1, 4}; int K = 7; List<List<int> > list = maxSubArray(arr, K); foreach(List<int> i in list) { Console.Write("["); foreach(int j in i) { Console.Write(j); if(i.Count > 1) Console.Write(","); } Console.Write("]"); }}}// This code is contributed by 29AjayKumar |
Javascript
<script>// js program to implement// the above approach// Function to return all possible// subarrays having product less// than or equal to Kfunction maxSubArray(arr, n, K){ // Store the required subarrays let solution = []; // Stores the product of // current subarray let multi = 1; // Stores the starting index // of the current subarray let start = 0; // Check for empty array if (n <= 1 || K < 0) { return solution; } // Iterate over the array for(let i = 0; i < n; i++) { // Calculate product multi = multi * arr[i]; // If product exceeds K while (multi > K) { // Reduce product multi =Math.floor( multi / arr[start]); // Increase starting index // of current subarray start++; } // Stores the subarray elements let list = []; // Store the subarray elements for(let j = i; j >= start; j--) { list.unshift(arr[j]); // Add the subarrays // to the list solution.push(list); } } // Return the final // list of subarrays return solution;}// Driver Code let arr = [ 2, 7, 1, 4 ]; let n = arr.length; let K = 7; let v = maxSubArray(arr, n, K); document.write( "["); let first = true; for(let x=0;x< v.length;x++) { if (!first) { document.write(", "); } else { first = false; } document.write( "["); let ff = true; for(let y =0;y<v[x].length;y++) { if (!ff) { document.write(", "); } else { ff = false; } document.write(v[x][y]); } document.write("]"); } document.write( "]");</script> |
Output
[[2], [7], [1], [7, 1], [4], [1, 4]]
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
