Given an array of positive integers arr[] of length N and a query array query[] of length M, the task is to find the maximum length subsequence in the array whose product is not greater than query [i] for all the queries.
Input: arr[] = {4, 5, 2, 1} queries[] = {3, 10, 21}
Output: {2, 3, 3}
Explanation:
For queries[0] : {2, 1} is maximum possible length subsequence in which product of all elements is not greater than query[0] i.e 3
For queries[1] : {4, 2, 1} is maximum possible length subsequence in which product of all elements is not greater than query[1] i.e 10
For queries[2] : {4, 2, 1} is maximum possible length subsequence in which product of all elements is not greater than query[2] i.e 21Input: arr[] = {7, 3, 2, 1, 0}, queries[] = {10, 20, 30}
Output: {5, 5, 5}
Explanation:
In array 0 is present, so for every query if we include 0 in maximum length subsequence then our product will be 0 which will always did not exceed the query value. For such all subsequence the maximum length will be total number of elements in array
Approach :
The length of the subsequence will be maximum if all the elements in the subsequence have minimum possible values. To achieve this we will sort the given array and for every query we will find the subarray length starting from 0 index whose product should not exceed the query value.
The corner case will be, if the 0 value is present in array then for every query maximum subsequence length will be total number of elements in array N as their product will be 0.
Illustration :
arr[] = { 4, 5, 2, 1} queries = { 3, 10, 21 },
Sort the given array so the new array becomes arr[] = {1, 2, 4, 5}
For query[0]:
=> The first 2 elements provide product less than 3.
=> The selected subsequence is highlighted {1, 2, 4, 5}
=> Maximum length subsequence will be of size 2.
For query[1]:
=> The first 3 elements provide product less than 10.
=> The selected subsequence is highlighted {1, 2, 4, 5}
=> Maximum length subsequence will be of size 3.
For query[2]:
=> The first 3 elements provide product less than 21.
=> The selected subsequence is highlighted {1, 2, 4, 5}
=> Maximum length subsequence will be of size 3.Hence, from queries array output generated will be {2, 3, 3}
Follow the below steps to Implement the above approach:
- Check the presence of 0 in the array
- If present then for each query[i] value greater than 0 return the length of the array.
- Else sort the array and then consider the maximum number of elements starting from index 0 that gives the product value less than query[i].
Below is the implementation of the above approach
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the length of the subsequence// with product less than each queryvector<int> maxLengthProductSubsequence(int arr[], int n, int queries[], int m){ vector<int> ans(m); // Sorting the given array sort(arr, arr + n); // Traverse for each query for (int i = 0; i < m; i++) { // To store current product and maximum product int curr_prod = 1, max_prod = queries[i]; // If query value is less than all elements value // the ans will be 0 ans[i] = 0; // Traverse in sorted array for (int j = 0; j < n; j++) { // Corner case if (arr[0] == 0) { ans[i] = n; break; } curr_prod *= arr[j]; if (curr_prod <= max_prod) { ans[i] = j + 1; } else { break; } } } return ans;}// Driver Codeint main(){ int arr[] = { 4, 5, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int queries[] = { 3, 10, 21 }; int M = sizeof(queries) / sizeof(arr[0]); // Function Call vector<int> res = maxLengthProductSubsequence(arr, N, queries, M); for (int x : res) cout << x << " "; return 0;} |
Java
// Java program to implement the approachimport java.util.*;class GFG{ // Function to find the length of the subsequence // with product less than each query static int[] maxLengthProductSubsequence(int arr[], int n, int queries[], int m) { int []ans = new int[m]; // Sorting the given array Arrays.sort(arr); // Traverse for each query for (int i = 0; i < m; i++) { // To store current product and maximum product int curr_prod = 1, max_prod = queries[i]; // If query value is less than all elements value // the ans will be 0 ans[i] = 0; // Traverse in sorted array for (int j = 0; j < n; j++) { // Corner case if (arr[0] == 0) { ans[i] = n; break; } curr_prod *= arr[j]; if (curr_prod <= max_prod) { ans[i] = j + 1; } else { break; } } } return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 4, 5, 2, 1 }; int N = arr.length; int queries[] = { 3, 10, 21 }; int M = queries.length; // Function Call int[] res = maxLengthProductSubsequence(arr, N, queries, M); for (int x : res) System.out.print(x+ " "); }}// This code is contributed by shikhasingrajput |
Python3
# Python code to implement the approach# Function to find the length of the subsequence# with product less than each querydef maxLengthProductSubsequence(arr, n, queries,m) : ans = [0] * m # Sorting the given array arr.sort() # Traverse for each query for i in range(m): # To store current product and maximum product curr_prod = 1 max_prod = queries[i] # If query value is less than all elements value # the ans will be 0 ans[i] = 0 # Traverse in sorted array for j in range(n): # Corner case if (arr[0] == 0) : ans[i] = n break curr_prod *= arr[j] if (curr_prod <= max_prod) : ans[i] = j + 1 else : break return ans# Driver Codeif __name__ == "__main__": arr = [ 4, 5, 2, 1 ] N = len(arr) queries = [ 3, 10, 21 ] M = len(queries) # Function Call res = maxLengthProductSubsequence(arr, N, queries, M) for x in res : print(x, end= " ")# This code is contributed by code_hunt. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the length of the subsequence // with product less than each query static int[] maxLengthProductSubsequence(int[] arr, int n, int[] queries, int m) { int []ans = new int[m]; // Sorting the given array Array.Sort(arr); // Traverse for each query for (int i = 0; i < m; i++) { // To store current product and maximum product int curr_prod = 1, max_prod = queries[i]; // If query value is less than all elements value // the ans will be 0 ans[i] = 0; // Traverse in sorted array for (int j = 0; j < n; j++) { // Corner case if (arr[0] == 0) { ans[i] = n; break; } curr_prod *= arr[j]; if (curr_prod <= max_prod) { ans[i] = j + 1; } else { break; } } } return ans; }static public void Main (){ int[] arr = { 4, 5, 2, 1 }; int N = arr.Length; int[] queries = { 3, 10, 21 }; int M = queries.Length; // Function Call int[] res = maxLengthProductSubsequence(arr, N, queries, M); foreach (int x in res) Console.Write(x+ " ");}}// This code is contributed by sanjoy_62. |
Javascript
// JavaScript program to implement the approach// Function to find the length of the subsequence// with product less than each queryfunction maxLengthProductSubsequence(arr, n, queries, m) { let ans = new Array(m); // Sorting the given array arr.sort(); // Traverse for each query for (let i = 0; i < m; i++) { // To store current product and maximum product let curr_prod = 1, max_prod = queries[i]; // If query value is less than all elements value // the ans will be 0 ans[i] = 0; // Traverse in sorted array for (let j = 0; j < n; j++) { // Corner case if (arr[0] == 0) { ans[i] = n; break; } curr_prod *= arr[j]; if (curr_prod <= max_prod) { ans[i] = j + 1; } else { break; } } } return ans;}// Driver Codelet arr = [4, 5, 2, 1];let N = arr.length;let queries = [3, 10, 21];let M = queries.length;// Function Calllet res = maxLengthProductSubsequence(arr, N, queries, M);console.log(res);// This code is contributed by ishankhandelwals. |
2 3 3
Time Complexity: O(M * N + N * logN), for each query it taken O(N) time. So total O(N*M) time to answer all M queries
Auxiliary Space: O(M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!