C++
// C++ code to find no. of subsets with// maximum difference d between max and#include <bits/stdc++.h>using namespace std;// function to calculate factorial of a numberint fact(int i){ if (i == 0) return 1; return i * fact(i - 1);}int ans(int a[], int n, int k, int x){ if (k > n || n < 1) return 0; sort(a, a + n); int count = 0; int j = 1; int i = 0; int kfactorial = fact(k); while (j <= n) { while (j < n && a[j] - a[i] <= x) { j++; } if ((j - i) >= k) { count = count + fact(j - i) / (kfactorial * fact(j - i - k)); } else { i++; j++; continue; } if (j == n) break; while (i < j && a[j] - a[i] > x) { i++; } if ((j - i) >= k) { count = count - fact(j - i) / (kfactorial * fact(j - i - k)); } } return count;}// driver program to test the above// functionint main(){ int arr[] = { 1, 12, 9, 2, 4, 2, 5, 8, 4, 6 }, k = 3,x = 5; int n = sizeof(arr) / sizeof(arr[0]); cout << ans(arr, n, k, x); return 0;}// This code is contributed by Vishakha Chauhan |
Java
// Java code to find no. of subsets with// maximum difference d between max and minimport java.io.*;import java.util.*;class GFG { // function to calculate factorial of a number static int fact(int i) { if (i == 0) { return 1; } return i * fact(i - 1); } static int ans(int[] a, int n, int k, int x) { if (k > n || n < 1) { return 0; } Arrays.sort(a); int count = 0, j = 1, i = 0; int kfactorial = fact(k); while (j <= n) { while (j < n && a[j] - a[i] <= x) { j++; } if ((j - i) >= k) { count = count + fact(j - i) / (kfactorial * fact(j - i - k)); } else { i++; j++; continue; } if (j == n) { break; } while (i < j && a[j] - a[i] > x) { i++; } if ((j - i) >= k) { count = count - fact(j - i) / (kfactorial * fact(j - i - k)); } } return count; } public static void main(String[] args) { int[] arr = { 1, 12, 9, 2, 4, 2, 5, 8, 4, 6 }; int k = 3, x = 5; int n = arr.length; System.out.print(ans(arr, n, k, x)); }}// This code is contributed by lokeshmvs21. |
C#
// C# code to find no. of subsets with// maximum difference d between max and minusing System;public class GFG{ // function to calculate factorial of a number static int fact(int i) { if (i == 0) { return 1; } return i * fact(i - 1); } static int ans(int[] a, int n, int k, int x) { if (k > n || n < 1) { return 0; } Array.Sort(a); int count = 0, j = 1, i = 0; int kfactorial = fact(k); while (j <= n) { while (j < n && a[j] - a[i] <= x) { j++; } if ((j - i) >= k) { count = count + fact(j - i) / (kfactorial * fact(j - i - k)); } else { i++; j++; continue; } if (j == n) { break; } while (i < j && a[j] - a[i] > x) { i++; } if ((j - i) >= k) { count = count - fact(j - i) / (kfactorial * fact(j - i - k)); } } return count; } static public void Main (){ // Code int[] arr = { 1, 12, 9, 2, 4, 2, 5, 8, 4, 6 }; int k = 3, x = 5; int n = arr.Length; Console.Write(ans(arr, n, k, x)); }}// This code is contributed by lokeshmvs21. |
Python3
class GFG : # function to calculate factorial of a number @staticmethod def fact( i) : if (i == 0) : return 1 return i * GFG.fact(i - 1) @staticmethod def ans( a, n, k, x) : if (k > n or n < 1) : return 0 a.sort() count = 0 j = 1 i = 0 kfactorial = GFG.fact(k) while (j <= n) : while (j < n and a[j] - a[i] <= x) : j += 1 if ((j - i) >= k) : count = count + int(GFG.fact(j - i) / (kfactorial * GFG.fact(j - i - k))) else : i += 1 j += 1 continue if (j == n) : break while (i < j and a[j] - a[i] > x) : i += 1 if ((j - i) >= k) : count = count - int(GFG.fact(j - i) / (kfactorial * GFG.fact(j - i - k))) return count @staticmethod def main( args) : arr = [1, 12, 9, 2, 4, 2, 5, 8, 4, 6] k = 3 x = 5 n = len(arr) print(GFG.ans(arr, n, k, x), end ="") if __name__=="__main__": GFG.main([]) |
Javascript
// function to calculate factorial of a numberfunction fact(i){ if (i == 0) { return 1; } return i * fact(i - 1);}function ans(a, n, k, x){ if (k > n || n < 1) { return 0; } a.sort(function(a, b) {return a - b;}); var count = 0; var j = 1; var i = 0; var kfactorial = fact(k); while (j <= n) { while (j < n && a[j] - a[i] <= x) { j++; } if ((j - i) >= k) { count = count + parseInt(fact(j - i) / (kfactorial * fact(j - i - k))); } else { i++; j++; continue; } if (j == n) { break; } while (i < j && a[j] - a[i] > x) { i++; } if ((j - i) >= k) { count = count - parseInt(fact(j - i) / (kfactorial * fact(j - i - k))); } } return count;} var arr = [1, 12, 9, 2, 4, 2, 5, 8, 4, 6]; var k = 3; var x = 5; var n = arr.length; console.log(ans(arr, n, k, x));// This code is contributed by sourabhdalal0001. |
Output
52
Algorithm:
1.The fact function takes an integer i as input and returns the factorial of that number using recursion. If the input is 0, it returns 1. Otherwise, it returns the product of i and the result of calling fact(i – 1).
2.The ans function takes an array a of integers, its length n, an integer k, and an integer x as inputs, and returns an integer representing the count of subsequences of length k in the array where the difference between the maximum and minimum element in the subsequence is at most x. If k is greater than n or n is less than 1, the function returns 0.
3.The function sorts the array in non-decreasing order using the sort function from the algorithm library.
4.It initializes count to 0, j to 1, and i to 0.
5.It calculates the factorial of k using the fact function and stores it in kfactorial.
6.It enters a while loop that runs while j is less than or equal to n.
7.Inside this loop, there is another loop that runs while j is less than n and the difference between a[j] and a[i] is less than or equal to x. This loop increments j by 1 in each iteration.
8.If the difference between j and i is greater than or equal to k, it calculates the count of subsequences using the formula fact(j-i) / (kfactorial * fact(j-i-k)) and adds it to count.
9.If the difference between j and i is less than k, it increments i and j by 1 and continues with the next iteration of the loop.
10.If j has reached the end of the array, the loop is broken.
11.There is another loop that runs while i is less than j and the difference between a[j] and a[i] is greater than x. This loop increments i by 1 in each iteration.
12.If the difference between j and i is greater than or equal to k, it calculates the count of subsequences using the formula -fact(j-i) / (kfactorial * fact(j-i-k)) and subtracts it from count.
13.The function returns the value of count.
Given an array and two integers k and d, find the number of subsets of this array of size k, where difference between the maximum and minimum number of the subset is atmost d.
Examples:
Input : a[] = [5, 4, 2, 1, 3],
k = 3, d = 5
Output : 10
Explanation:
{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5},
{1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}.
We can see each subset has atmost
difference d=5 between the minimum
and maximum element of each subset.
No of such subsets = 10
Input : a[] = [1, 2, 3, 4, 5, 6],
k = 3, d = 5
Output : 20
Naive approach: Finding all the subsets of size k and for each subset find the difference between maximum and minimum element. If the difference is less than or equal to d, count them.
Efficient approach :
- Sorting: First sort the array in increasing order. Now, assume we want to find out for each ith element, the number of required subsets in which integer a[i] is present as the minimum element of that subset. The maximum in such a subset will never exceed a[i] + d .
- Find maximum index j : We can apply binary search over this array for each i, to find the maximum index j, such that a[j] <= a[i]+d . Now any subset that includes a[i] and any other elements from the range i+1…j will be a required subset as because element a[i] is the minimum of that subset, and the difference between any other element and a[i] is always less than equal to d.
- Apply basic combinatorics formula : Now we want to find the number of required subsets of size k. This will be by using the basic formula of combination when you have to select r items from given n numbers. In the same way we need to choose (k-1) numbers from (j-i) elements already including a[i] which is the minimum number in each subset. The sum of this procedure for each ith element will be the final answer.
Here I have used a simple recursive way to find factorial of a number one can use dynamic programming as well to find it.
Illustration :
Input : a = [5, 4, 2, 1, 3],
k = 3, d = 5
Output : 10Explanation:
Sorted array in ascending order : [1, 2, 3, 4, 5]
For a[0] = 1 as minimum element
No. of subset will be 6 which are {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}.
For a[1] = 2 as minimum element
No. of subset will be 3 which are {2, 3, 4}, {2, 3, 5}, {2, 4, 5}
For a[2] = 3 as minimum element
No. of subset will be 1 which is {3, 4, 5}
No other subset of size k = 3 will be formed
by taking a[3] = 4 or a[4] = 5 as minimum element
C++
// C++ code to find no. of subsets with // maximum difference d between max and// min of all K-size subsets function to// calculate factorial of a number#include <bits/stdc++.h>using namespace std;int fact (int n){ if (n==0) return 1; else return n * fact(n-1);}// function to count ways to select r// numbers from n given numbersint findcombination (int n,int r){ return( fact(n) / (fact(n - r) * fact(r)));}// function to return the total number // of required subsets :// n is the number of elements in array// d is the maximum difference between// minimum and maximum element in each// subset of size k int find(int arr[], int n, int d, int k){ sort(arr,arr+n); int ans = 0, end = n, co = 0, start = 0; // loop to traverse from 0-n for (int i = 0; i < n; i++) { int val = arr[i] + d; // binary search to get the position // which will be stored in start start = i; while (start < end - 1){ int mid = (start + end) / 2; // if mid value greater than // arr[i]+d do search in // arr[start:mid] if (arr[mid] > val) end = mid; else start = mid + 1; } if (start != n and arr[start] <= val) start += 1; int c = start-i; // if the numbers of elements 'c' // is greater or equal to the given // size k, then only subsets of // required size k can be formed if (c >= k){ co += findcombination(c - 1, k - 1);} } return co;}// driver program to test the above// functionint main(){ int arr[] = {1, 2, 3, 4, 5, 6}, k = 3, d = 5; int n = sizeof(arr) / sizeof(arr[0]); cout << find(arr, n,d,k); return 0;}// This code is contributed by Prerna Saini |
Java
// Java code to find no. of subsets // with maximum difference d between// max and min of all K-size subsetsimport java.util.*;class GFG {// function to calculate factorial // of a numberstatic int fact (int n){ if (n==0) return 1; else return n * fact(n-1);}// function to count ways to select r// numbers from n given numbersstatic int findcombination(int n, int r){ return( fact(n) / (fact(n - r) * fact(r)));}// function to return the total number// of required subsets :// n is the number of elements in array// d is the maximum difference between // minimum and maximum element in each// subset of size k static int find(int arr[], int n, int d, int k){ Arrays.sort(arr); int ans = 0, end = n, co = 0, start = 0; // loop to traverse from 0-n for (int i = 0; i < n; i++) { int val = arr[i] + d; // binary search to get the position // which will be stored in start start=i; while (start < end - 1){ int mid = (start + end) / 2; // if mid value greater than // arr[i]+d do search in // arr[start:mid] if (arr[mid] > val) end = mid; else start = mid+1; } if (start !=n && arr[start] <= val) start += 1; int c = start-i; // if the numbers of elements 'c' is // greater or equal to the given size k, // then only subsets of required size k // can be formed if (c >= k){ co += findcombination(c - 1, k - 1);} } return co;}// driver program to test the above functionpublic static void main(String[] args){ int arr[] = {1, 2, 3, 4, 5, 6}, k = 3, d = 5; int n = arr.length; System.out.println(find(arr, n,d,k));}}// This code is contributed by Prerna Saini |
Python
# Python code to find no. of subsets with maximum # difference d between max and min of all K-size # subsets function to calculate factorial of a # numberdef fact (n): if (n==0): return (1) else: return n * fact(n-1)# function to count ways to select r numbers# from n given numbersdef findcombination (n,r): return( fact(n)//(fact(n-r)*fact(r)))# function to return the total number of required # subsets :# n is the number of elements in list l[0..n-1]# d is the maximum difference between minimum and# maximum element in each subset of size k def find (a, n, d, k): # sort the list first in ascending order a.sort() (start, end, co) = (0, n, 0) for i in range(0, n): val = a[i]+ d # binary search to get the position # which will be stored in start # such that a[start] <= a[i]+d start = i while (start< end-1): mid = (start+end)//2 # if mid value greater than a[i]+d # do search in l[start:mid] if (a[mid] > val): end = mid # if mid value less or equal to a[i]+d # do search in a[mid+1:end] else: start = mid+1 if (start!=n and a[start]<=val): start += 1 # count the numbers of elements that fall # in range i to start c = start-i # if the numbers of elements 'c' is greater # or equal to the given size k, then only # subsets of required size k can be formed if (c >= k): co += findcombination(c-1,k-1) return co# Driver coden = 6 # Number of elementsd = 5 # maximum diffk = 3 # Size of subsetsprint(find([1, 2, 3, 4, 5, 6], n, d, k)) |
C#
// C# code to find no. of subsets // with maximum difference d between// max and min of all K-size subsetsusing System;class GFG { // function to calculate factorial // of a number static int fact (int n) { if (n == 0) return 1; else return n * fact(n - 1); } // function to count ways to select r // numbers from n given numbers static int findcombination(int n, int r) { return( fact(n) / (fact(n - r) * fact(r))); } // function to return the total number // of required subsets : // n is the number of elements in array // d is the maximum difference between // minimum and maximum element in each // subset of size k static int find(int []arr, int n, int d, int k) { Array.Sort(arr); //int ans = 0, int end = n, co = 0, start = 0; // loop to traverse from 0-n for (int i = 0; i < n; i++) { int val = arr[i] + d; // binary search to get the // position which will be // stored in start start = i; while (start < end - 1){ int mid = (start + end) / 2; // if mid value greater than // arr[i]+d do search in // arr[start:mid] if (arr[mid] > val) end = mid; else start = mid+1; } if (start !=n && arr[start] <= val) start += 1; int c = start-i; // if the numbers of elements 'c' is // greater or equal to the given size k, // then only subsets of required size k // can be formed if (c >= k) co += findcombination(c - 1, k - 1); } return co; } // driver program to test the above function public static void Main() { int []arr = {1, 2, 3, 4, 5, 6}; int k = 3; int d = 5; int n = arr.Length; Console.WriteLine(find(arr, n, d, k)); }}// This code is contributed by anuj_67. |
PHP
<?php// Php code to find no. of subsets with // maximum difference d between max and// min of all K-size subsets function to// calculate factorial of a number function fact ($n){ if ($n==0) return 1; else return $n * fact($n-1);} // function to count ways to select r// numbers from n given numbersfunction findcombination ($n,$r){ return( fact($n) / (fact($n - $r) * fact($r)));} // function to return the total number // of required subsets :// n is the number of elements in array// d is the maximum difference between// minimum and maximum element in each// subset of size k function find(&$arr, $n, $d, $k){ sort($arr); $ans = 0; $end = $n; $co = 0; $start = 0; // loop to traverse from 0-n for ($i = 0; $i < $n; $i++) { $val = $arr[$i] + $d; // binary search to get the position // which will be stored in start $start = $i; while ($start < $end - 1){ $mid = intval (($start + $end) / 2); // if mid value greater than // arr[i]+d do search in // arr[start:mid] if ($arr[$mid] > $val) $end = $mid; else $start = $mid + 1; } if ($start != $n && $arr[$start] <= $val) $start += 1; $c = $start-$i; // if the numbers of elements 'c' // is greater or equal to the given // size k, then only subsets of // required size k can be formed if ($c >= $k){ $co += findcombination($c - 1, $k - 1);} } return $co;} // driver program to test the above// function $arr = array(1, 2, 3, 4, 5, 6); $k = 3; $d = 5; $n = sizeof($arr) / sizeof($arr[0]); echo find($arr, $n,$d,$k); return 0;?> |
Javascript
<script>// Javascript code to find no. of subsets // with maximum difference d between// max and min of all K-size subsets // function to calculate factorial // of a number function fact(n) { let answer=1; if (n == 0 || n == 1) { return answer;} else { for(var i = n; i >= 1; i--){ answer = answer * i; } return answer; } }// function to count ways to select r// numbers from n given numbersfunction findcombination(n,r){ return( Math.floor(fact(n) / (fact(n - r) * fact(r))));}// function to return the total number// of required subsets :// n is the number of elements in array// d is the maximum difference between // minimum and maximum element in each// subset of size k function find(arr, n, d, k){ arr.sort(function(a, b){return a-b;}); let ans = 0, end = n, co = 0, start = 0; // loop to traverse from 0-n for (let i = 0; i < n; i++) { let val = arr[i] + d; // binary search to get the position // which will be stored in start start=i; while (start < end - 1){ let mid = Math.floor((start + end) / 2); // if mid value greater than // arr[i]+d do search in // arr[start:mid] if (arr[mid] > val) end = mid; else start = mid+1; } if (start !=n && arr[start] <= val) start += 1; let c = start-i; // if the numbers of elements 'c' is // greater or equal to the given size k, // then only subsets of required size k // can be formed if (c >= k){ co += findcombination(c - 1, k - 1);} } return co;}// driver program to test the above functionlet arr = [1, 2, 3, 4, 5, 6];let k = 3, d = 5;let n = arr.length;document.write(find(arr, n, d, k)); // This code is contributed by rag2127.</script> |
Output
20
Time Complexity: O(N logN), where N represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
This article is contributed by Sruti Rai . If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
