Given an array arr[ ] of length N consisting cost of N toys and an integer K depicting the amount with you. Your task is to find maximum number of toys you can buy with K amount. 
Example 1:
Input: 
N = 7 
K = 50
arr[] = {1, 12, 5, 111, 200, 1000, 10}
Output: 4
Explaination: The costs of the toys 
you can buy are 1, 12, 5 and 10.
Example 2:
Input: 
N = 3 
K = 100
arr[] = {20, 30, 50}
Output: 3
Explaination: You can buy all toys.
Your Task:
You do not need to read input or print anything. Your task is to complete the function toyCount() which takes the integer N, integer K and the array arr[ ] as input parameters and returns the maximum count of toys you can have.
Expected Time Complexity: O(N * Log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ K, arr[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def toyCount(self, N, K, arr):
        # code here


Solutions:
class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		i = 0
		while K > 0 and i < N:
			K -= arr[i]
			i += 1
		if i == N:
			return i
		else:
			return i - 1


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		cost = 0
		n = 0
		for i in range(N):
			cost += arr[i]
			if cost > K:
				break
			n += 1
		return n


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		c = 0
		for i in range(N):
			if c < K:
				c += arr[i]
			else:
				break
		if c > K:
			return i - 1
		else:
			return i + 1


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		sum = 0
		ans = 0
		for i in arr:
			sum = sum + i
			if sum < K:
				ans += 1
			elif sum == K:
				ans += 1
				return ans
			else:
				return ans
		return ans


class Solution:

	def toyCount(self, N, K, arr):
		c = 0
		arr.sort()
		s = 0
		for i in range(len(arr)):
			if arr[i] <= K:
				c += 1
				K -= arr[i]
		return c


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		c = 0
		s = 0
		for i in arr:
			s += i
			if s <= K:
				c += 1
			elif s > K:
				break
		return c


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		s = 0
		a = []
		for i in arr:
			s += i
			if s <= K:
				a.append(i)
		return len(a)


class Solution:

	def toyCount(self, N, K, arr):
		(res, currTym) = (0, 0)
		arr.sort()
		for i in range(N):
			currTym += arr[i]
			if currTym > K:
				break
			res += 1
		return res


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		for i in range(N):
			if arr[i] <= K:
				K -= arr[i]
			else:
				return i
		return N


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		A = [arr[0]]
		for i in range(1, N):
			A.append(A[i - 1] + arr[i])
		return self.search(A, 0, N - 1, K)

	def search(self, A, l, h, k):
		if l > h:
			return N
		mid = (l + h) // 2
		if A[mid] == k:
			return mid + 1
		if A[mid] > k and A[mid - 1] < k:
			return mid
		if A[mid] < k:
			return self.search(A, mid + 1, h, k)
		else:
			return self.search(A, l, mid - 1, k)


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		count = 0
		for i in range(N):
			if arr[i] <= K:
				count += 1
				K = K - arr[i]
		return count


class Solution:

	def toyCount(self, N, k, arr):
		arr.sort()
		i = 0
		c = 0
		while k >= 0 and i < N:
			c += 1
			k = k - arr[i]
			i += 1
		if k < 0:
			return c - 1
		else:
			return c


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		sum = 0
		count = 0
		for value in arr:
			if sum + value <= K:
				sum += value
				count += 1
			else:
				break
		return count


class Solution:

	def toyCount(self, N, K, arr):
		arr = sorted(arr)
		sum_ = 0
		count = 0
		for i in range(N):
			if K - arr[i] >= 0:
				sum_ += arr[i]
				K -= arr[i]
				count += 1
			else:
				break
		return count


class Solution:

	def toyCount(self, N, K, arr):
		lst = []
		arr.sort()
		for i in range(N):
			if K >= arr[i]:
				lst.append(arr[i])
				K -= arr[i]
		return len(lst)


class Solution:

	def toyCount(self, N, K, arr):
		arr_sorted = sorted(arr)
		count = 0
		total_price = 0
		for price in arr_sorted:
			if total_price + price > K:
				return count
			else:
				count += 1
				total_price += price
		return count


class Solution:

	def toyCount(self, N, K, arr):
		sum = 0
		c = 0
		l = []
		for i in range(N):
			if arr[i] <= K:
				l.append(arr[i])
		l.sort()
		for i in range(len(l)):
			if sum <= K:
				sum += l[i]
				c += 1
		if sum > K:
			sum -= l[i - 1]
			c -= 1
		return c


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		(wstart, wend) = (0, 0)
		s = 0
		ans = 0
		while wend < N:
			s += arr[wend]
			if s <= K:
				ans = max(ans, wend - wstart + 1)
			if s > K:
				while s > K:
					s -= arr[wstart]
					wstart += 1
			wend += 1
		return ans


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		cost = 0
		ind = 0
		while cost < K and N > ind:
			cost += arr[ind]
			ind += 1
		if cost > K:
			ind -= 1
		return ind


class Solution:

	def toyCount(self, N, K, arr):
		price = 0
		count = 0
		if sum(arr) <= K:
			return len(arr)
		else:
			for i in sorted(arr):
				if price <= K:
					price += i
					count += 1
		return count - 1


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		sum = 0
		cnt = 0
		for i in range(N):
			if sum + arr[i] > K:
				break
			sum += arr[i]
			cnt += 1
		return cnt


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		i = 0
		cnt = 0
		while i < N and arr[i] <= K:
			(i, K, cnt) = (i + 1, K - arr[i], cnt + 1)
		return cnt


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		temp = 0
		res = 0
		for i in arr:
			res += 1
			temp += i
			if temp == K:
				return res
			elif temp > K:
				return res - 1
		return res


class Solution:

	def toyCount(self, N, k, arr):
		c = 0
		d = 0
		arr.sort()
		for i in arr:
			c += i
			if c > k:
				break
			else:
				d += 1
		return d


class Solution:

	def toyCount(self, n, k, arr):
		arr.sort()
		i = 0
		count = 0
		while i < n and k - arr[i] >= 0 and (i < n):
			count += 1
			k -= arr[i]
			i += 1
		return count


class Solution:

	def toyCount(self, N, K, arr):
		s = 0
		j = 0
		a = [i for i in arr if i < K]
		p = sorted(a)
		for i in range(len(p)):
			if s + p[i] <= K:
				s += p[i]
				j += 1
		return j


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		t = 0
		i = 0
		while K >= 0 and i < N:
			if K - arr[i] < 0:
				break
			K -= arr[i]
			i += 1
			t += 1
		return t


class Solution:

	def toyCount(self, n, k, arr):
		arr.sort()
		i = 0
		c = 0
		while i < n and k > 0:
			if arr[i] <= k:
				c += 1
				k -= arr[i]
			i += 1
		return c


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		count = 0
		tot = 0
		for i in arr:
			if tot + i <= K:
				tot += i
				count += 1
			else:
				break
		return count


class Solution:

	def toyCount(self, n, k, arr):
		arr.sort()
		c = 0
		count = 0
		for i in range(n):
			c += arr[i]
			if c <= k:
				count += 1
		return count


class Solution:

	def toyCount(self, N, K, arr):
		arr = sorted(arr)
		count = 0
		s = 0
		for i in range(0, len(arr)):
			if arr[i] + s <= K:
				count += 1
				s = s + arr[i]
		return count


class Solution:

	def toyCount(self, N, k, arr):
		arr.sort()
		s = 0
		cnt = 0
		for i in arr:
			s += i
			if s > k:
				return cnt
			else:
				cnt += 1
		return cnt


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		(ans, pre, i) = (0, 0, 0)
		while i < N:
			pre += arr[i]
			if pre > K:
				break
			ans += 1
			i += 1
		return ans


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		c = 0
		t = sum(arr)
		if K >= t:
			return N
		while c < N and arr[c] <= K:
			K -= arr[c]
			t -= arr[c]
			c += 1
		return c


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		fsum = 0
		for i in range(N):
			fsum += arr[i]
			if fsum > K:
				return i
		return N


class Solution:

	def toyCount(self, N, K, arr):
		c = 0
		a = sorted(arr)
		for i in a:
			if i <= K:
				c += 1
				K -= i
		return c


class Solution:

	def toyCount(self, N, K, arr):
		arr.sort()
		i = 0
		s = 0
		while i < N:
			s = s + arr[i]
			if s > K:
				return i
			i += 1
		return N


class Solution:

	def toyCount(self, N, K, arr):
		toy = 0
		arr.sort()
		bill = 0
		for i in range(N):
			if bill + arr[i] > K:
				exit
			else:
				bill += arr[i]
				toy += 1
		return toy