Count of subsequences with a sum in range [L, R] and difference between max and min element at least X
Given an array arr[] consisting of N positive integers and 3 integers L, R, and X, the task is to find the number of subsequences of size atleast 2 with a sum in the range [L, R], and the difference between the maximum and minimum element is at least X. (N≤15)
Examples:
Input: arr[] = {1 2 3}, L = 5, R = 6, X = 1
Output: 2
Explanation:
There are two subsequences possible i.e. {2, 3} and {1, 2, 3}.Input: arr[] = {10, 20, 30, 25}, L = 40, R = 50, X = 10
Output: 2
Approach: Since N is small, this problem can be solved using bitmasking. There are total 2n subsequences possible. So, every subsequence can be represented by a binary string i.e. mask where if the ith bit is set i.e 1 then the element is considered in the subsequences otherwise not. Follow the steps below to solve the problem:
- Iterate in the range [0, 2n – 1] using the variable i and perform the following steps:
- Initialize a variable say, cnt as 0 and sum as 0 to store the sum of selected elements.
- Initialize a variable say, minVal as INT_MAX and maxVal as INT_MIN to store minimum value and maximum value in the subsequence.
- Iterate in the range [0, N-1] using the variable j and perform the following steps:
- If the jth bit of the ith mask is on, then Increment cnt by 1, add arr[j] to sum and update maxVal as the maximum of maxVal and a[j] and minVal as the minimum of minVal and a[j].
- If cnt >= 2 and sum is in the range [L, R] and the difference of maxVal and minVal is greater than equal to X, then increment ans by 1.
- After completing the above steps, print the value of ans as the answer.
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 number of subsequences // of the given array with a sum in range [L, R] // and the difference between the maximum and // minimum element is at least X int numberofSubsequences( int a[], int L, int R, int X, int n) { // Initialize answer as 0 int ans = 0; // Creating mask from [0, 2^n-1] for ( int i = 0; i < (1 << n); i++) { // Stores the count and sum of // selected elements respectively int cnt = 0, sum = 0; // Variables to store the value of // Minimum and maximum element int minVal = INT_MAX, maxVal = INT_MIN; // Traverse the array for ( int j = 0; j < n; j++) { // If the jth bit of the ith // mask is on if ((i & (1 << j))) { cnt += 1; // Add the selected element sum += a[j]; // Update maxVal and minVal value maxVal = max(maxVal, a[j]); minVal = min(minVal, a[j]); } } // Check if the given conditions are // true, increment ans by 1. if (cnt >= 2 && sum >= L && sum <= R && (maxVal - minVal >= X)) { ans += 1; } } return ans; } // Driver Code int main() { // Given Input int a[] = { 10, 20, 30, 25 }; int L = 40, R = 50, X = 10; int N = sizeof (a) / sizeof (a[0]); // Function Call cout << numberofSubsequences(a, L, R, X, N) << endl; return 0; } |
Java
// Java program for the above approach public class GFG { // Function to find the number of subsequences // of the given array with a sum in range [L, R] // and the difference between the maximum and // minimum element is at least X static int numberofSubsequences( int a[], int L, int R, int X, int n) { // Initialize answer as 0 int ans = 0 ; // Creating mask from [0, 2^n-1] for ( int i = 0 ; i < ( 1 << n); i++) { // Stores the count and sum of // selected elements respectively int cnt = 0 , sum = 0 ; // Variables to store the value of // Minimum and maximum element int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE; // Traverse the array for ( int j = 0 ; j < n; j++) { // If the jth bit of the ith // mask is on if ((i & ( 1 << j)) == 0 ) { cnt += 1 ; // Add the selected element sum += a[j]; // Update maxVal and minVal value maxVal = Math.max(maxVal, a[j]); minVal = Math.min(minVal, a[j]); } } // Check if the given conditions are // true, increment ans by 1. if (cnt >= 2 && sum >= L && sum <= R && (maxVal - minVal >= X)) { ans += 1 ; } } return ans; } // Driver code public static void main(String[] args) { int a[] = { 10 , 20 , 30 , 25 }; int L = 40 , R = 50 , X = 10 ; int N = a.length; // Function Call System.out.println( numberofSubsequences(a, L, R, X, N)); } } // This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach import sys # Function to find the number of subsequences # of the given array with a sum in range [L, R] # and the difference between the maximum and # minimum element is at least X def numberofSubsequences(a, L, R, X, n): # Initialize answer as 0 ans = 0 # Creating mask from [0, 2^n-1] for i in range ( 0 , ( 1 << n), 1 ): # Stores the count and sum of # selected elements respectively cnt = 0 sum = 0 # Variables to store the value of # Minimum and maximum element minVal = sys.maxsize maxVal = - sys.maxsize - 1 # Traverse the array for j in range (n): # If the jth bit of the ith # mask is on if ((i & ( 1 << j))): cnt + = 1 # Add the selected element sum + = a[j] # Update maxVal and minVal value maxVal = max (maxVal, a[j]) minVal = min (minVal, a[j]) # Check if the given conditions are # true, increment ans by 1. if (cnt > = 2 and sum > = L and sum < = R and (maxVal - minVal > = X)): ans + = 1 return ans # Driver Code if __name__ = = '__main__' : # Given Input a = [ 10 , 20 , 30 , 25 ] L = 40 R = 50 X = 10 N = len (a) # Function Call print (numberofSubsequences(a, L, R, X, N)) # This code is contributed by bgangwar59 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the number of subsequences // of the given array with a sum in range [L, R] // and the difference between the maximum and // minimum element is at least X static int numberofSubsequences( int [] a, int L, int R, int X, int n) { // Initialize answer as 0 int ans = 0; // Creating mask from [0, 2^n-1] for ( int i = 0; i < (1 << n); i++) { // Stores the count and sum of // selected elements respectively int cnt = 0, sum = 0; // Variables to store the value of // Minimum and maximum element int minVal = Int32.MaxValue, maxVal = Int32.MinValue; // Traverse the array for ( int j = 0; j < n; j++) { // If the jth bit of the ith // mask is on if ((i & (1 << j)) == 0) { cnt += 1; // Add the selected element sum += a[j]; // Update maxVal and minVal value maxVal = Math.Max(maxVal, a[j]); minVal = Math.Min(minVal, a[j]); } } // Check if the given conditions are // true, increment ans by 1. if (cnt >= 2 && sum >= L && sum <= R && (maxVal - minVal >= X)) { ans += 1; } } return ans; } // Driver Code static public void Main() { // Given input int [] a = { 10, 20, 30, 25 }; int L = 40, R = 50, X = 10; int N = a.Length; // Function Call Console.Write(numberofSubsequences(a, L, R, X, N)); } } // This code is contributed by avijitmondal1998 |
Javascript
<script> // Javascript program for the above approach // Function to find the number of subsequences // of the given array with a sum in range [L, R] // and the difference between the maximum and // minimum element is at least X function numberofSubsequences(a, L, R, X, n) { // Initialize answer as 0 let ans = 0; // Creating mask from [0, 2^n-1] for (let i = 0; i < (1 << n); i++) { // Stores the count and sum of // selected elements respectively let cnt = 0, sum = 0; // Variables to store the value of // Minimum and maximum element let minVal = Number.MAX_SAFE_INTEGER, maxVal = Number.MIN_SAFE_INTEGER; // Traverse the array for (let j = 0; j < n; j++) { // If the jth bit of the ith // mask is on if ((i & (1 << j))) { cnt += 1; // Add the selected element sum += a[j]; // Update maxVal and minVal value maxVal = Math.max(maxVal, a[j]); minVal = Math.min(minVal, a[j]); } } // Check if the given conditions are // true, increment ans by 1. if (cnt >= 2 && sum >= L && sum <= R && (maxVal - minVal >= X)) { ans += 1; } } return ans; } // Driver Code // Given Input let a = [10, 20, 30, 25]; let L = 40, R = 50, X = 10; let N = a.length; // Function Call document.write(numberofSubsequences(a, L, R, X, N) + "<br>" ); // This code is contributed by gfgking. </script> |
2
Time Complexity: O(N×2N)
Auxiliary Space: O(1)