Given n buckets and infinite number of balls. The maximum capacity of each bucket is given in an array capacity[]. Find the number of ways to fill the buckets with balls such that each bucket has atleast 1 ball and all the buckets have distinct number of balls in them.
Note: Since the answer may be very large, calculate the answer modulo 10^9+7.
Example 1:
Input: 
n = 1
capacity = [6]
Output: 6
Explanation: Since there is only one 
bucket. It may hold any number of balls 
ranging from 1 to 6.
Example 2:
Input: 
n = 2 
capacity = [5, 8]
Output: 35
Explanation: If the first bucket has 1
ball in it then the second bucket cant have 1 
ball, so the second bucket has 8-1 = 7 choices.
So the first bucket has 5 choices and for each
choice second bucket has 7 choices.
So total there are 35 ways.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function totalWays() which takes n and capacity[] as input parameters and returns the number of possible ways to fill the buckets. Since the answer may be very large, calculate the answer modulo 10^9+7.
Expected Time Complexity: O(n*log(n)) 
Expected Space Complexity: O(1)
Constraints:
1 <= n <= 100000
1 <= capacity[i] <= 100000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Combinatorics

Starter code: #User function Template for python3



class Solution:

	def totalWays(self, n, capacity):

		# code here

Solutions:
class Solution:

	def totalWays(self, n, capacity):
		res = 1
		M = 10 ** 9 + 7
		capacity.sort()
		for i in range(n):
			res = res * (capacity[i] - i) % M
		return res


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		ans = 1
		for i in range(len(capacity)):
			ans = ans % 1000000007 * ((capacity[i] - i) % 1000000007) % 1000000007
		return ans


from heapq import heapify, heappop

class Solution:

	def totalWays(self, n, c):
		heapify(c)
		ans = 1
		z = 0
		for i in range(len(c)):
			val = heappop(c)
			ans *= val - z
			ans %= 10 ** 9 + 7
			z += 1
		return ans % (10 ** 9 + 7)


class Solution:

	def totalWays(self, n, capacity):
		a = sorted(capacity)
		p = a[0]
		for i in range(1, n):
			p *= a[i] - i
			p %= 1000000007
		return p


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		ways = 1
		mod = 10 ** 9 + 7
		for i in range(len(capacity)):
			ways = ways * (capacity[i] - i) % mod
		return ways


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		ans = 1
		mod = 1000000007
		for i in range(n):
			ans = ans * (capacity[i] - i) % mod
		return int(ans % mod)


class Solution:

	def totalWays(self, n, capacity):
		x = 1000000007
		ways = 1
		capacity.sort()
		for i in range(n):
			ways = ways * (capacity[i] - i) % x
		return ways


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		count = capacity[0]
		for i in range(1, n):
			count = count * (capacity[i] - i)
			count = count % 1000000007
		return count


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		ans = capacity[0]
		for i in range(1, n):
			ans = ans % (10 ** 9 + 7) * (capacity[i] - i) % (10 ** 9 + 7)
		return ans % (10 ** 9 + 7)


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		a = 1
		mod = 1000000007
		for i in range(n):
			a = a * (capacity[i] - i) % mod
		return a % mod


class Solution:

	def totalWays(self, n, capacity):
		s = sorted(capacity)
		a = 1
		for i in range(len(s)):
			a = a % 1000000007 * (s[i] - i) % 1000000007
		return a


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		ans = 1
		mod = 1000000000.0 + 7
		for i in range(0, n):
			ans = ans * (capacity[i] - i)
			ans = ans % mod
		return int(ans)


P = 10 ** 9 + 7

class Solution:

	def totalWays(self, n, arr):
		arr.sort()
		ans = 1
		for i in range(n):
			ans = ans * (arr[i] - i) % P
		return ans


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		M = int(1000000000.0) + 7
		count = 0
		res = 1
		for i in capacity:
			res = res * (i - count) % M
			count += 1
		return res


from numpy import sort

class Solution:

	def totalWays(self, n, capacity):
		s = sort(capacity)
		result = 1
		for i in range(n):
			t = s[i]
			result = result % 1000000007 * ((t - i) % 1000000007) % 1000000007
		return result


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		(ans, MOD) = (1, 1000000007)
		for (i, cap) in enumerate(capacity):
			ans = ans * (cap - i) % MOD
		return ans


class Solution:

	def totalWays(self, n, capacity):
		MOD = 1000000007
		capacity.sort()
		ans = capacity[0]
		for i in range(1, n):
			ans = ans * (capacity[i] - i) % MOD
		return ans


class Solution:

	def totalWays(self, n, cap):
		mod = 1000000007
		cap.sort()
		ans = cap[0]
		for i in range(1, n):
			ans = ans % mod * ((cap[i] - i) % mod) % mod
		return ans


from itertools import combinations
MODULO = 10 ** 9 + 7

class Solution:

	def totalWays(self, n, capacity):
		res = 1
		capacity.sort()
		for i in range(n):
			res = res % MODULO * (capacity[i] - i) % MODULO
		return res


class Solution:

	def totalWays(self, n, capacity):
		ans = 1
		mod = pow(10, 9) + 7
		capacity = sorted(capacity)
		for i in range(n - 1, 0, -1):
			ans = ans * (capacity[i] - i) % mod
		ans = ans * capacity[0] % mod
		return ans % mod


class Solution:

	def totalWays(self, n, capacity):
		ans = 1
		capacity = sorted(capacity)
		for i in range(n - 1, -1, -1):
			ans = ans * (capacity[i] - i) % 1000000007
		return ans % 1000000007


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		k = 0
		res = 1
		for each in capacity:
			res = res * (each - k) % 1000000007
			k = k + 1
		return res


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		s = 1
		x = 10 ** 9 + 7
		for i in range(n):
			s *= capacity[i] - i
			s = s % x
		return s


class Solution:

	def totalWays(self, n, capacity):
		arr = capacity
		arr.sort()
		n = len(capacity)
		a = 1
		for i in range(n):
			a = a * (arr[i] - i) % (1000000000.0 + 7)
		return int(a)


class Solution:

	def totalWays(self, n, capacity):
		num = 1
		capacity.sort()
		mod = 1000000007
		for item in range(n):
			num = num % mod * (capacity[item] - item) % mod
		return num


def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

class Solution:

	def totalWays(self, n, c):
		c.sort()
		ans = 1
		r = 1000000007
		for i in range(n):
			ans = ans * (capacity[i] - i)
			ans %= r
		return ans


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		result = 1
		mod = 10 ** 9 + 7
		for index in range(len(capacity)):
			result = result * (capacity[index] - index) % mod
		return int(result % mod)


class Solution:

	def totalWays(self, n, c):
		c = sorted(c)
		k = c[0]
		for i in range(1, len(c)):
			k = k % (10 ** 9 + 7) * ((c[i] - i) % (10 ** 9 + 7))
		return k % (10 ** 9 + 7)


class Solution:

	def totalWays(self, n, capacity):
		if n == 1:
			return capacity[0]
		x = 1
		mod = 1000000007
		capacity.sort()
		for i in range(0, n):
			y = capacity[i] - i
			x = x * y % mod
		return x


class Solution:

	def totalWays(self, n, capacity):
		import heapq
		ans = 1
		if n == 1:
			ans = capacity[0]
		else:
			heapq.heapify(capacity)
			i = 0
			while capacity:
				z = heapq.heappop(capacity)
				ans = ans * (z - i) % 1000000007
				i += 1
		return ans


class Solution:

	def totalWays(self, n, capacity):
		Num = 1
		capacity.sort()
		for i in range(n):
			Num = Num * (capacity[i] - i) % 1000000007
		return Num % 1000000007


class Solution:

	def totalWays(self, n, capacity):
		mod = 10 ** 9 + 7
		capacity.sort()
		flag = False
		ans = 1
		for i in range(n - 1, -1, -1):
			if capacity[i] < i:
				flag = True
				break
			else:
				ans = ans % mod * (capacity[i] - i) % mod % mod
		if flag:
			return 0
		return ans


class Solution:

	def totalWays(self, n, capacity):
		capacity.sort()
		result = capacity[0]
		for i in range(1, len(capacity)):
			bucket_possibilites = capacity[i] - i
			result = result * bucket_possibilites % (10 ** 9 + 7)
		return result


class Solution:

	def totalWays(self, n, capacity):
		mod = 1000000007
		capacity.sort()
		ans = capacity[0]
		count = 1
		if n == 1:
			return ans
		else:
			for i in range(1, len(capacity)):
				ans = ans * (capacity[i] - count)
				count += 1
				ans = ans % mod
		return ans


class Solution:

	def totalWays(self, n, capacity):
		m = 1000000007
		capacity.sort()
		sum = 1
		for i in range(len(capacity)):
			sum *= capacity[i] - i
			sum = sum % m
		return sum


class Solution:

	def totalWays(self, n, capacity):
		p = pow(10, 9) + 7
		count = 0
		capacity.sort()
		m = 1
		for i in capacity:
			m = m * (i - count) % p
			count = count + 1
		return m


class Solution:

	def totalWays(self, n, c):
		c.sort()
		m = 10 ** 9 + 7
		ans = 1
		for i in range(n):
			ans = ans * (c[i] - i) % m
		return ans