Given an array arr consisting of integers of size n and 2 additional integers k and x, you need to find the number of subsets of this array of size k, where Absolute difference between the Maximum and Minimum number of the subset is at most x.
Note: As this number that you need to find can be rather large, print it Modulo 10^{9}+7
 
Example 1:
Input:
n = 5, k = 3, x = 5
arr[] = {1, 2, 3, 4, 5}
Output:
10
Explanation :
Possible subsets of size 3 are :-
{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} having difference
of maximum and minimum
element less than equal to 5.
 
Example 2:
Input:
n = 8, k = 4, x = 6
arr[] = {2, 4, 6, 8, 10, 12, 14, 16}
Output:
5
Explanation :
Possible subsets of size 4 are:-
{2,4,6,8} {4,6,8,10} {6,8,10,12}
{8,10,12,14} {10,12,14,16} having
difference of maximum and minimum 
element less than equal to 6.
Your Task:
You don't have to print anything, printing is done by the driver code itself. Your task is to complete the function getAnswer() which takes the array arr[], its size n and two integers k and x as inputs and returns the required result, Modulo 10^{9}+7.
 
Expected Time Complexity: O(n. log(n))
Expected Auxiliary Space: O(n)
 
Constraints:
1 ≤ n ≤ 5×10^{5}
1 ≤ k ≤ n
1 ≤ arr[i], x ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



def getAnswer( arr, n, k, x):

    # Your code goes here

Solutions:
def inv(a, m):
	b = m - 2
	ans = 1
	while b:
		if b & 1:
			ans = ans * a % m
		a = a * a % m
		b >>= 1
	return ans

def getAnswer(arr, n, k, x):
	M = int(1000000000.0 + 7)
	arr.sort()
	ans = 0
	j = 0
	fact = [1] * (n + 1)
	for i in range(1, n + 1):
		fact[i] = fact[i - 1] * i % M
	for i in range(n):
		while j < n and arr[j] - arr[i] <= x:
			j += 1
		if j - i >= k:
			ans = (ans + fact[j - i - 1] * inv(fact[k - 1] * fact[j - i - k], M) % M) % M
	return ans


from math import factorial

def getAnswer(arr, n, k, x):
	arr.sort()
	count = 0
	f = factorial(k - 1)
	j = k - 1
	for i in range(n - k + 1):
		while j < n and arr[j] - arr[i] <= x:
			j += 1
		if j - i >= k and arr[j - 1] - arr[i] <= x:
			count += factorial(j - i - 1) // f // factorial(j - i - k)
	return count % (10 ** 9 + 7)


import bisect as bi

def fact(n):
	if n == 0:
		return 1
	return n * fact(n - 1)

def comb(c, k):
	return fact(c) // (fact(c - k) * fact(k))

def getAnswer(arr, n, k, x):
	arr.sort()
	ans = 0
	for i in range(n):
		f = 1
		v = arr[i] + x
		p = bi.bisect(arr, v)
		p -= 1
		if p == n - 1:
			if arr[n - 1] - arr[i] > x:
				f = 0
			else:
				pass
		elif arr[p] > v:
			f = 0
		if f != 0:
			c = p - i + 1
			if c >= k:
				ans += comb(c - 1, k - 1)
	return ans % 1000000007


def getAnswer(arr, n, k, x):
	arr = sorted(arr, reverse=False)
	count = 0
	MOD = 10 ** 9 + 7
	for i in range(len(arr)):
		end = len(arr) - 1
		val = arr[i] + x
		start = i
		while start < end:
			mid = start + (end - start) // 2
			if arr[mid] > val:
				end = mid
			else:
				start = mid + 1
		if arr[start] <= val:
			start += 1
		c = start - i
		if c >= k:
			count += combinations(c - 1, k - 1)
	return count % MOD

def combinations(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r))

def factorial(n):
	if n == 0:
		return 1
	return n * factorial(n - 1)