Given three positive integers, L, R, K and an array arr[] consisting of N positive integers, the task is to count the number of ways to select at least K array elements from the given array having values in the range [L, R].
Examples:
Input: arr[] = {12, 4, 6, 13, 5, 10}, K = 3, L = 4, R = 10
Output: 5
Explanation:
Possible ways to select at least K(= 3) array elements having values in the range [4, 10] are: { (arr[1], arr[2], arr[4]), (arr[1], arr[2], arr[5]), (arr[1], arr[4], arr[5]), (arr[2], arr[4], arr[5]), (arr[1], arr[2], arr[4], arr[5]) }
Therefore, the required output is 5.Input: arr[] = {1, 2, 3, 4, 5}, K = 4, L = 1, R = 5
Output: 6
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say cntWays, to store the count of ways to select at least K array elements having values lies in the range [L, R].
- Initialize a variable, say cntNum to store the count of numbers in the given array whose values lies in the range given range.
- Finally, print the sum of all possible value of
such that (K + i) is less than or equal to cntNum.
such that (K + i) is less than or equal to cntNum.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 calculate factorial// of all the numbers up to Nvector<int> calculateFactorial(int N){ vector<int> fact(N + 1); // Factorial of 0 is 1 fact[0] = 1; // Calculate factorial of // all the numbers upto N for (int i = 1; i <= N; i++) { // Calculate factorial of i fact[i] = fact[i - 1] * i; } return fact;}// Function to find the count of ways to select// at least K elements whose values in range [L, R]int cntWaysSelection(int arr[], int N, int K, int L, int R){ // Stores count of ways to select at least // K elements whose values in range [L, R] int cntWays = 0; // Stores count of numbers having // value lies in the range [L, R] int cntNum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Checks if the array elements // lie in the given range if (arr[i] >= L && arr[i] <= R) { // Update cntNum cntNum++; } } // Stores factorial of numbers upto N vector<int> fact = calculateFactorial(cntNum); // Calculate total ways to select at least // K elements whose values lies in [L, R] for (int i = K; i <= cntNum; i++) { // Update cntWays cntWays += fact[cntNum] / (fact[i] * fact[cntNum - i]); } return cntWays;}// Driver Codeint main(){ int arr[] = { 12, 4, 6, 13, 5, 10 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; int L = 4; int R = 10; cout << cntWaysSelection(arr, N, K, L, R);} |
Java
// Java program to implement// the above approachclass GFG{// Function to calculate factorial// of all the numbers up to Nstatic int[] calculateFactorial(int N){ int []fact = new int[N + 1]; // Factorial of 0 is 1 fact[0] = 1; // Calculate factorial of // all the numbers upto N for (int i = 1; i <= N; i++) { // Calculate factorial of i fact[i] = fact[i - 1] * i; } return fact;}// Function to find the count of ways to select// at least K elements whose values in range [L, R]static int cntWaysSelection(int arr[], int N, int K, int L, int R){ // Stores count of ways to select at least // K elements whose values in range [L, R] int cntWays = 0; // Stores count of numbers having // value lies in the range [L, R] int cntNum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Checks if the array elements // lie in the given range if (arr[i] >= L && arr[i] <= R) { // Update cntNum cntNum++; } } // Stores factorial of numbers upto N int []fact = calculateFactorial(cntNum); // Calculate total ways to select at least // K elements whose values lies in [L, R] for (int i = K; i <= cntNum; i++) { // Update cntWays cntWays += fact[cntNum] / (fact[i] * fact[cntNum - i]); } return cntWays;}// Driver Codepublic static void main(String[] args){ int arr[] = { 12, 4, 6, 13, 5, 10 }; int N = arr.length; int K = 3; int L = 4; int R = 10; System.out.print(cntWaysSelection(arr, N, K, L, R));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement the# above approach# Function to calculate factorial # of all the numbers up to Ndef calculateFactorial(N): fact = [0] * (N + 1) # Factorial of 0 is 1 fact[0] = 1 # Calculate factorial of all # the numbers upto N for i in range(1, N + 1): # Calculate factorial of i fact[i] = fact[i - 1] * i return fact# Function to find count of ways to select# at least K elements whose values in range[L,R]def cntWaysSelection(arr, N, K, L, R): # Stores count of ways to select at leas # K elements whose values in range[L,R] cntWays = 0 # Stores count of numbers having # Value lies in the range[L,R] cntNum = 0 # Traverse the array for i in range(0, N): # Check if the array elements # Lie in the given range if (arr[i] >= L and arr[i] <= R): # Update cntNum cntNum += 1 # Stores factorial of numbers upto N fact = list(calculateFactorial(cntNum)) # Calculate total ways to select at least # K elements whose values Lies in [L,R] for i in range(K, cntNum + 1): # Update cntWays cntWays += fact[cntNum] // (fact[i] * fact[cntNum - i]) return cntWays # Driver codeif __name__ == "__main__": arr = [ 12, 4, 6, 13, 5, 10 ] N = len(arr) K = 3 L = 4 R = 10 print(cntWaysSelection(arr, N, K, L, R))# This code is contributed by Virusbuddah |
C#
// C# program to implement// the above approachusing System; class GFG{ // Function to calculate factorial// of all the numbers up to Nstatic int[] calculateFactorial(int N){ int[] fact = new int[(N + 1)]; // Factorial of 0 is 1 fact[0] = 1; // Calculate factorial of // all the numbers upto N for(int i = 1; i <= N; i++) { // Calculate factorial of i fact[i] = fact[i - 1] * i; } return fact;} // Function to find the count of ways to select// at least K elements whose values in range [L, R]static int cntWaysSelection(int[] arr, int N, int K, int L, int R){ // Stores count of ways to select at least // K elements whose values in range [L, R] int cntWays = 0; // Stores count of numbers having // value lies in the range [L, R] int cntNum = 0; // Traverse the array for(int i = 0; i < N; i++) { // Checks if the array elements // lie in the given range if (arr[i] >= L && arr[i] <= R) { // Update cntNum cntNum++; } } // Stores factorial of numbers upto N int[] fact = calculateFactorial(cntNum); // Calculate total ways to select at least // K elements whose values lies in [L, R] for(int i = K; i <= cntNum; i++) { // Update cntWays cntWays += fact[cntNum] / (fact[i] * fact[cntNum - i]); } return cntWays;} // Driver Codepublic static void Main() { int[] arr = { 12, 4, 6, 13, 5, 10 }; int N = arr.Length; int K = 3; int L = 4; int R = 10; Console.WriteLine(cntWaysSelection( arr, N, K, L, R));}}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program to implement// the above approach// Function to calculate factorial// of all the numbers up to Nfunction calculateFactorial(N){ var fact = Array(N + 1); // Factorial of 0 is 1 fact[0] = 1; // Calculate factorial of // all the numbers upto N for (var i = 1; i <= N; i++) { // Calculate factorial of i fact[i] = fact[i - 1] * i; } return fact;}// Function to find the count of ways to select// at least K elements whose values in range [L, R]function cntWaysSelection(arr, N, K, L, R){ // Stores count of ways to select at least // K elements whose values in range [L, R] var cntWays = 0; // Stores count of numbers having // value lies in the range [L, R] var cntNum = 0; // Traverse the array for (var i = 0; i < N; i++) { // Checks if the array elements // lie in the given range if (arr[i] >= L && arr[i] <= R) { // Update cntNum cntNum++; } } // Stores factorial of numbers upto N var fact = calculateFactorial(cntNum); // Calculate total ways to select at least // K elements whose values lies in [L, R] for (var i = K; i <= cntNum; i++) { // Update cntWays cntWays += fact[cntNum] / (fact[i] * fact[cntNum - i]); } return cntWays;}// Driver Codevar arr = [ 12, 4, 6, 13, 5, 10 ];var N = arr.length;var K = 3;var L = 4;var R = 10;document.write( cntWaysSelection(arr, N, K, L, R));</script> |
Output:
5
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
