Let Max be the maximum possible mean of a multiset of values obtained from an array Arr of length N. Let Min be the minimum possible mean of a multiset of values obtained from the same array. Note that in a multiset values may repeat. The task is to find the number of multisets with mean as Max and the number of multisets with mean as Min. The answer may be too large so output the number of multisets modulo 10^{9}+7. 
 
Example 1:
Input:
N = 5
Arr = {3, 1, 2, 3, 4} 
Output:
1 1
Explanation:
The maximum possible Mean of a Subset
of the array is 4. There can be only 1
such subset - {3, 1, 2, 3, 4}.
The minimum possible Mean of a Subset
of the array is 1. There can be only 1
such subset - {3, 1, 2, 3, 4}.
Example 2:
Input:
N = 3
Arr = {1, 2, 1} 
Output:
1 3
Explanation:
The maximum possible Mean of a Subset
of the array is 2. There can be only 1
such subset - {1, 2, 1}.
The minimum possible Mean of a Subset
of the array is 1. There can be 3 such
subsets - {1, 2, 1}; {1, 2, 1}; {1, 2, 1}.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function numOfSubsets() which takes an Integer N and an array Arr[] as input and returns a vector of two numbers- the number of multisets with mean as Max and the number of multisets with mean as Min.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}
1 <= Arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def numOfSubsets(self, Arr , N):

        # code here

Solutions:
class Solution:

	def numOfSubsets(self, A, n):
		mod = 1000000007
		mn = min(A)
		mx = max(A)
		mnc = 0
		mxc = 0
		for x in A:
			if x == mn:
				mnc += 1
			if x == mx:
				mxc += 1
		r1 = 1
		r2 = 1
		while mnc > 0:
			mnc -= 1
			r1 = 2 * r1 % mod
		while mxc > 0:
			mxc -= 1
			r2 = 2 * r2 % mod
		return ((r2 - 1 + mod) % mod, (r1 - 1 + mod) % mod)


class Solution:

	def numOfSubsets(self, Arr, N):
		maxi = -float('inf')
		mini = float('inf')
		sol = []
		for i in range(N):
			if maxi < Arr[i]:
				maxi = Arr[i]
			if mini > Arr[i]:
				mini = Arr[i]
		(count_max, count_min) = (0, 0)
		for i in range(N):
			if Arr[i] == maxi:
				count_max += 1
			if Arr[i] == mini:
				count_min += 1
		(ans1, ans2) = (0, 0)
		ans1 = pow(2, count_max) - 1
		ans2 = pow(2, count_min) - 1
		return [ans1, ans2]


class Solution:

	def numOfSubsets(self, Arr, N):
		mi = 1000000007
		ma = -1000000007
		for i in Arr:
			mi = min(mi, i)
			ma = max(ma, i)
		no_ma = 0
		no_mi = 0
		for i in Arr:
			if i == mi:
				no_mi += 1
			if i == ma:
				no_ma += 1
		no_ma = (2 ** no_ma - 1) % 1000000007
		no_mi = (2 ** no_mi - 1) % 1000000007
		return [no_ma, no_mi]


class Solution:

	def numOfSubsets(self, Arr, N):
		mi = Arr[0]
		ma = Arr[0]
		for a in Arr:
			mi = min(mi, a)
			ma = max(ma, a)
		cnt_mi = 0
		cnt_ma = 0
		for a in Arr:
			if a == mi:
				cnt_mi += 1
			if a == ma:
				cnt_ma += 1
		return [(2 ** cnt_ma - 1) % (10 ** 9 + 7), (2 ** cnt_mi - 1) % (10 ** 9 + 7)]


from collections import defaultdict

class Solution:

	def numOfSubsets(self, Arr, N):
		_count = defaultdict(lambda : 0)
		for num in Arr:
			_count[num] += 1
		min_key = min_val = None
		max_key = max_val = None
		for (key, val) in _count.items():
			if not min_key or key < min_key:
				(min_key, min_val) = (key, val)
			if not max_key or key > max_key:
				(max_key, max_val) = (key, val)
		return ((2 ** max_val - 1) % (10 ** 9 + 7), (2 ** min_val - 1) % (10 ** 9 + 7))


MIN = pow(10, 9) + 7

class Solution:

	def numOfSubsets(self, Arr, N):
		d = {}
		mx = -1
		mn = MIN
		for a in Arr:
			if a in d.keys():
				d[a] += 1
			else:
				d[a] = 1
			mn = min(mn, a)
			mx = max(mx, a)
		return [pow(2, d[mx]) - 1, pow(2, d[mn]) - 1]


class Solution:

	def numOfSubsets(self, Arr, N):
		m = max(Arr)
		n = min(Arr)
		maxcount = Arr.count(m)
		mincount = Arr.count(n)
		return [2 ** maxcount - 1, 2 ** mincount - 1]


class Solution:

	def numOfSubsets(self, Arr, N):
		largest = max(Arr)
		smallest = min(Arr)
		freqLargest = 0
		freqSmallest = 0
		for i in range(len(Arr)):
			if Arr[i] == largest:
				freqLargest += 1
			if Arr[i] == smallest:
				freqSmallest += 1
		l = int((2 ** freqLargest - 1) % (1000000000.0 + 7))
		s = int((2 ** freqSmallest - 1) % (1000000000.0 + 7))
		return [l, s]


import sys

class Solution:

	def numOfSubsets(self, Arr, N):
		max_val = -sys.maxsize
		min_val = sys.maxsize
		freq = {}
		for num in Arr:
			freq[num] = freq.get(num, 0) + 1
			max_val = max(max_val, num)
			min_val = min(min_val, num)
		max_subset = pow(2, freq[max_val]) - 1
		min_subset = pow(2, freq[min_val]) - 1
		return [max_subset, min_subset]


class Solution:

	def numOfSubsets(self, Arr, N):
		from collections import Counter
		c = Counter(Arr)
		(min_v, max_v) = (min(Arr), max(Arr))
		return (2 ** c[max_v] - 1, 2 ** c[min_v] - 1)


from collections import Counter

class Solution:

	def numOfSubsets(self, Arr, N):
		counter = Counter(Arr)
		min_val = min(Arr)
		max_val = max(Arr)
		return (2 ** counter[max_val] - 1, 2 ** counter[min_val] - 1)


import sys

class Solution:

	def numOfSubsets(self, Arr, N):
		max = -sys.maxsize
		min = sys.maxsize
		max_count = 0
		min_count = 0
		for num in Arr:
			if num > max:
				max = num
				max_count = 1
			elif num == max:
				max_count += 1
			if num < min:
				min = num
				min_count = 1
			elif num == min:
				min_count += 1
		return (pow(2, max_count, pow(10, 9) + 7) - 1, pow(2, min_count, pow(10, 9) + 7) - 1)


class Solution:

	def numOfSubsets(self, arr, N):
		massimo = max(arr)
		minimo = min(arr)
		cont_massimo = arr.count(massimo)
		cont_minimo = arr.count(minimo)
		m = 10 ** 9 + 7
		return (pow(2, cont_massimo, m) - 1, pow(2, cont_minimo, m) - 1)


class Solution:

	def numOfSubsets(self, Arr, N):
		max_num = Arr[0]
		max_count = 1
		min_num = Arr[0]
		min_count = 1
		for i in range(1, N):
			if Arr[i] > max_num:
				max_num = Arr[i]
				max_count = 1
			elif Arr[i] == max_num:
				max_count += 1
			if Arr[i] < min_num:
				min_num = Arr[i]
				min_count = 1
			elif Arr[i] == min_num:
				min_count += 1
		return [(2 ** max_count - 1) % (10 ** 9 + 7), (2 ** min_count - 1) % (10 ** 9 + 7)]


class Solution:

	def numOfSubsets(self, Arr, N):
		freq = {}
		maxi = Arr[0]
		mini = Arr[0]
		for elem in Arr:
			if elem > maxi:
				maxi = elem
			if elem < mini:
				mini = elem
			if elem not in freq:
				freq[elem] = 1
			else:
				freq[elem] += 1
		c = 1000000007
		ret1 = 2 ** freq[maxi] % c - 1
		ret2 = 2 ** freq[mini] % c - 1
		return [ret1, ret2]


class Solution:

	def power(self, a, b, m):
		a = a % m
		r = 1
		while b > 0:
			if b & 1:
				r = r * a % m
			a = a * a % m
			b >>= 1
		return r

	def numOfSubsets(self, a, n):
		a.sort()
		m = 10 ** 9 + 7
		mi = a.count(a[0])
		ma = a.count(a[-1])
		ans1 = self.power(2, ma, m)
		ans2 = self.power(2, mi, m)
		return (ans1 - 1, ans2 - 1)


class Solution:

	def numOfSubsets(self, a, n):
		a.sort()
		m = 10 ** 9 + 7
		mi = a.count(a[0])
		ma = a.count(a[-1])
		ans1 = ans2 = 1
		for i in range(ma):
			ans1 = ans1 * 2 % m
		for i in range(mi):
			ans2 = ans2 * 2 % m
		return (ans1 - 1, ans2 - 1)


class Solution:

	def numOfSubsets(self, Arr, N):
		modulo = 1000000000.0 + 7
		max_value = max(Arr)
		min_value = min(Arr)
		max_occurrences = 0
		min_occurrences = 0
		for a in Arr:
			if a == max_value:
				max_occurrences += 1
			if a == min_value:
				min_occurrences += 1

		def fac(x):
			f = x
			for i in range(2, x):
				f *= i
			return f

		def ziehen(n, k):
			if n == k:
				return 1
			return fac(n) // fac(n - k) // fac(k)
		x = 0
		for i in range(1, max_occurrences + 1):
			x += ziehen(max_occurrences, i)
			x = x % modulo
		y = 0
		for i in range(1, min_occurrences + 1):
			y += ziehen(min_occurrences, i)
			y = y % modulo
		return (int(x), int(y))


class Solution:

	def numOfSubsets(self, arr, N):
		max_subset_num = self.getComb(arr, max(arr))
		min_subset_num = self.getComb(arr, min(arr))
		return (max_subset_num, min_subset_num)

	def getComb(self, arr, val):
		cnt = arr.count(val)
		output = 2 ** cnt - 1
		return output


class Solution:

	def numOfSubsets(self, arr, n):
		(mx, mn) = (0, 10 ** 6)
		for i in range(n):
			if arr[i] > mx:
				mx = arr[i]
			if arr[i] < mn:
				mn = arr[i]
		(a, b) = (1, 1)
		m = 10 ** 9 + 7
		for i in range(n):
			if arr[i] == mx:
				a = a % m * 2 % m
			if arr[i] == mn:
				b = b % m * 2 % m
		return [a - 1, b - 1]


class Solution:

	def numOfSubsets(self, Arr, N):
		max_ = max(Arr)
		min_ = min(Arr)
		Max = len([ar for ar in Arr if ar == max_])
		Min = len([ar for ar in Arr if ar == min_])
		max_subsets = 2 ** Max - 1
		min_subsets = 2 ** Min - 1
		return (max_subsets, min_subsets)


class Solution:

	def numOfSubsets(self, Arr, N):
		countMax = Arr.count(max(Arr))
		countMin = Arr.count(min(Arr))
		return ((2 ** countMax - 1) % (10 ** 9 + 7), (2 ** countMin - 1) % (10 ** 9 + 7))


def power(x, y, p):
	res = 1
	while y > 0:
		if y % 2 == 0:
			x = x * x % p
			y //= 2
		else:
			res *= x % p
			y -= 1
	return res % p

class Solution:

	def numOfSubsets(self, a, N):
		x1 = max(a)
		y1 = a.count(x1)
		x2 = min(a)
		y2 = a.count(x2)
		p = 10 ** 9 + 7
		(ans1, ans2) = (power(2, y1, p), power(2, y2, p))
		ans1 = (ans1 % p - 1 % p) % p
		ans2 = (ans2 % p - 1 % p) % p
		return (ans1, ans2)


from collections import defaultdict

class Solution:

	def numOfSubsets(self, Arr, N):
		dp = defaultdict(int)
		minn = float('inf')
		maxx = float('-inf')
		for e in Arr:
			dp[e] += 1
			minn = min(e, minn)
			maxx = max(e, maxx)
		return [(2 ** dp[maxx] - 1) % (10 ** 9 + 7), (2 ** dp[minn] - 1) % (10 ** 9 + 7)]


class Solution:

	def numOfSubsets(self, Arr, N):
		max_ele = max(Arr)
		min_ele = min(Arr)
		max_ele_count = Arr.count(max_ele)
		min_ele_count = Arr.count(min_ele)
		return (2 ** max_ele_count - 1, 2 ** min_ele_count - 1)