## Problem

Given an Array consisting of N integers, we need to find the number of subsets of this Array of size K, where Absolute difference between the Maximum and Minimum element of the subset is at most X.

## Explanation

Lets say given Array is `[4 5 1 3 2]` and `K=3` and `X=5`

number of subsets satisfying given conditions will be `10`

One of the subset is `[1 2 5]` having K elements and absolute difference between minimum and maximum element less then X i.e `5-1<X`

## Solution

This problem comes under easy-medium level.
Formally a k-combination of a set S is a subset of k distinct elements of S

1. First sort the Array
`[1 2 3 4 5]`
• Fix the first element.

• Then traverse the array, counting elements whose difference with fixed element is less than or equal to X.

• Calculate K-1 combinations of (counted elements - fixed element’s index), if (counted elements - fixed element’s index) is greater then `k-1` .
`K-1` because one element is fixed.

• Fix the next element and repeat from step 3.

• Repeat above step `length(array)-1` times.

## For large arrays using modulo

For arrays small than 20 elemets we can find combinations directly `nCr = n! / (r! * (n-r)!)`

For arrays large than 20 elements finding combinations goes out of integer limit. So we have to calculate nCr modulo M

If we have to calcuate nCr mod p(where p is a prime), we can calculate factorial mod p and then use modular inverse to find nCr mod p. If we have to find nCr mod m(where m is not prime), we can factorize m into primes and then use Chinese Remainder Theorem(CRT) to find nCr mod m.