You are given N ropes. A cut operation is performed on ropes such that all of them are reduced by the length of the smallest rope. Display the number of ropes left after every cut operation until the length of each rope is zero.
Example 1:
Input : arr[ ] = {5, 1, 1, 2, 3, 5} 
Output : 4 3 2 
Explanation: In the first operation, the 
minimum ropes are 1 So, we reduce length 1 
from all of them after reducing we left with 
4 ropes and we do the same for rest. 
 
Example 2:
Input : arr[ ] = {5, 1, 6, 9, 8, 11, 2, 
                               2, 6, 5} 
Output :  9 7 5 3 2 1
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function RopeCutting() that takes an array (arr), sizeOfArray (n), and return the number of ropes that are left after each operation with space if no ropes left after one operation, in this case, return 0. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def RopeCutting (self, arr, n) : 

        #Complete the function

    

  

Solutions:
class Solution:

	def __init__(self):
		self.lst = []

	def RopeCutting(self, arr, n):
		Ropes = arr
		Ropes.sort()
		singleOperation = 0
		cuttingLength = Ropes[0]
		for i in range(1, n):
			if Ropes[i] - cuttingLength > 0:
				self.lst.append(n - i)
				cuttingLength = Ropes[i]
				singleOperation += 1
		if singleOperation == 0:
			return 0
		return self.lst


class Solution:

	def RopeCutting(self, arr, n):
		l = []
		arr.sort()
		for i in range(n - 1):
			if arr[i] != arr[i + 1]:
				l.append(n - i - 1)
		return l


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		l = []
		i = 1
		c = 1
		k = n
		while n != 0 and i < n:
			if arr[i] == arr[i - 1]:
				c += 1
			else:
				l.append(k - c)
				k = k - c
				c = 1
			i += 1
		return l


class Solution:

	def RopeCutting(self, arr, n):
		arr = sorted(arr)
		ans = []
		cur = arr[0]
		for i in range(1, n):
			if arr[i] - cur > 0:
				ans.append(n - i)
				cur += arr[i] - cur
		return ans


class Solution:

	def RopeCutting(self, arr, n):
		a = []
		arr.sort()
		t = arr[0]
		for i in range(n):
			if arr[i] != t:
				t = arr[i]
				a += [n - i]
		return a


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		ac = 0
		idx = 0
		res = []
		for (i, x) in enumerate(arr):
			if i < idx:
				continue
			ac = x
			while idx < n and arr[idx] <= ac:
				idx += 1
			if idx == n:
				break
			res.append(n - idx)
		return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort(reverse=True)
		output = []
		while arr:
			mini = arr[-1]
			while arr and arr[-1] == mini:
				arr.pop()
			output.append(len(arr))
		output.pop()
		return output


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		a = []
		mini = arr[0]
		for i in range(1, n):
			if arr[i] - mini > 0:
				a.append(n - i)
				mini = arr[i]
		return a


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		min_val = arr[0]
		temp = []
		count = 0
		for i in range(1, n):
			if arr[i] - min_val > 0:
				temp.append(n - i)
				min_val = arr[i]
				count += 1
		if count == 0:
			return 0
		return temp


class Solution:

	def RopeCutting(self, a, n):
		a.sort()
		m = a[0]
		b = []
		for i in range(n):
			if a[i] - m > 0:
				b.append(n - i)
			m = a[i]
		return b


class Solution:

	def RopeCutting(self, arr, n):
		res = []
		sorted_arr = sorted(arr)
		min_val = sorted_arr[0]
		for i in range(n):
			if sorted_arr[i] - min_val > 0:
				min_val = sorted_arr[i]
				res.append(n - i)
		return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		res = []
		left = 0
		mincut = arr[0]
		for i in range(1, n):
			if arr[i] - mincut > 0:
				res.append(n - i)
				mincut = arr[i]
				left += 1
		if left == 0:
			return 0
		else:
			return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		res = []
		small = arr[0]
		for i in range(1, n):
			if arr[i] != small:
				small = arr[i]
				res = res + [n - i]
		return res


class Solution:

	def RopeCutting(self, arr, n):
		if n == 1:
			return [0]
		arr.sort()
		ans = []
		i = 0
		c = n
		while i < n:
			el = arr[i]
			while i < n and arr[i] - el == 0:
				c -= 1
				i += 1
			ans.append(c)
		ans.pop()
		return ans


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		new_arr = []
		curr_elem = arr[0]
		for i in range(len(arr)):
			if arr[i] != curr_elem:
				curr_elem = arr[i]
				new_arr.append(len(arr) - i)
		return new_arr


class Solution:

	def RopeCutting(self, arr, n):
		freq = {}
		for i in range(n):
			if arr[i] not in freq:
				freq[arr[i]] = 1
			else:
				freq[arr[i]] += 1
		it = list(freq.items())
		it.sort(key=lambda x: x[0])
		res = []
		s = 0
		for i in range(len(it) - 1):
			s += it[i][1]
			res.append(n - s)
		return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		result = []
		current_ropes = arr[0]
		for i in range(n):
			if arr[i] - current_ropes > 0:
				result.append(n - i)
				current_ropes = arr[i]
		return result


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		l = []
		singleOperation = 0
		cuttingLength = arr[0]
		for i in range(1, n):
			if arr[i] - cuttingLength > 0:
				print(n - i, end=' ')
				cuttingLength = arr[i]
				singleOperation += 1
		if singleOperation == 0:
			print('0')
		return l


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		a = []
		temp = arr[0]
		for i in range(len(arr)):
			if arr[i] != temp:
				temp = arr[i]
				a += [n - i]
		return a


import bisect

class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		rsf = 0
		res = []
		cut = 0
		while cut < n:
			rsf = arr[cut]
			cut = bisect.bisect_right(arr, rsf)
			if cut == n:
				break
			res.append(n - cut)
		return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		i = 0
		res = []
		length = n
		while i < n:
			cnt = 1
			i += 1
			while i < n and arr[i] == arr[i - 1]:
				cnt += 1
				i += 1
			res.append(length - cnt)
			length -= cnt
		if len(res) == 1:
			return [0]
		return res[:-1]


class Solution:

	def RopeCutting(self, arr, n):
		arr = sorted(arr)
		i = 0
		size = []
		cut_len = 0
		while i < n:
			while i < n - 1 and arr[i] == arr[i + 1]:
				i += 1
			if i < n - 1:
				cut_len += arr[i]
				size.append(n - i - 1)
			i += 1
		if len(size) == 0:
			size.append(0)
		return size


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		cuts = []
		cutting_element = arr[0]
		for i in range(1, n):
			res = arr[i] - cutting_element
			if res > 0:
				cuts.append(n - i)
				cutting_element = arr[i]
		return cuts


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		ans = []
		cut_len = arr[0]
		for i in range(n):
			if arr[i] - cut_len > 0:
				cut_len = arr[i]
				ans.append(n - i)
		return ans


class Solution:

	def RopeCutting(self, arr, n):
		ans = []
		arr.sort()
		cutting_length = arr[0]
		i = 1
		while i < n:
			if arr[i] - cutting_length > 0:
				ans.append(n - i)
			cutting_length = arr[i]
			i += 1
		return ans


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		res = []
		for x in range(n - 1):
			if arr[x] != arr[x + 1]:
				res.append(n - x - 1)
		return res


class Solution:

	def RopeCutting(self, arr, n):
		l = []
		arr.sort()
		h = arr[0]
		for i in range(n):
			if arr[i] != h:
				h = arr[i]
				l += [n - i]
		return l


class Solution:

	def RopeCutting(self, arr, n):
		arr = sorted(arr)
		res = []
		arr.append(0)
		(i, j) = (0, 1)
		while True:
			while arr[j] == arr[i]:
				j += 1
			if j == n:
				break
			res.append(n - j)
			i = j
			j += 1
		return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		arr_len = len(arr)
		starting_elem = arr[0]
		result = []
		for i in range(1, arr_len):
			if arr[i] == starting_elem:
				continue
			else:
				starting_elem = arr[i]
				result.append(arr_len - i)
		return result


class Solution:

	def RopeCutting(self, arr, n):
		if n <= 1:
			return n
		arr.sort()
		self.m = arr[0]
		self.C = []
		for i in range(1, n):
			if arr[i] - self.m > 0:
				self.C.append(n - i)
				self.m = arr[i]
		return self.C


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		min_rope = arr[0]
		res = []
		for i in range(n):
			if arr[i] - min_rope > 0:
				res.append(n - i)
				min_rope = arr[i]
		return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		c = arr[0]
		x = []
		for i in range(n):
			if arr[i] != c:
				c = arr[i]
				x.append(n - i)
		return x


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		i = 0
		t = arr[0]
		li = []
		while i < n:
			if arr[i] != t:
				li += [n - i]
				t = arr[i]
			i += 1
		return li
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.RopeCutting(arr, n)
	print(*res)


class Solution:

	def RopeCutting(self, arr, n):
		l = []
		arr.sort()
		for i in range(n - 1):
			if arr[i] != arr[i + 1]:
				l.append(n - i - 1)
		return l
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.RopeCutting(arr, n)
	print(*res)


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		sp = 0
		ar = []
		cut = arr[0]
		for i in range(1, n):
			if arr[i] - cut > 0:
				ar.append(n - i)
				cut = arr[i]
				sp += 1
		if sp == 0:
			return '0'
		else:
			return ar
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.RopeCutting(arr, n)
	print(*res)


class Solution:

	def RopeCutting(self, arr, n):
		arr = sorted(arr)
		res = []
		arr.append(0)
		(i, j) = (0, 1)
		while True:
			while arr[j] == arr[i]:
				j += 1
			if j == n:
				break
			res.append(n - j)
			i = j
			j += 1
		return res
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.RopeCutting(arr, n)
	print(*res)


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		cutlen = arr[0]
		lst = []
		for i in range(1, n):
			if arr[i] - cutlen > 0:
				lst.append(n - i)
				cutlen = arr[i]
		return lst


class Solution:

	def RopeCutting(self, arr, n):
		a = []
		count = n
		arr.sort()
		for i in range(n - 1):
			count -= 1
			if arr[i] < arr[i + 1]:
				a.append(count)
		if arr[-1] > arr[-2] and count > 1:
			count -= 1
			a.append(count)
		return a


class Solution:

	def RopeCutting(self, a, n):
		a.sort()
		li = []
		min1 = 1
		n1 = n
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				min1 += 1
				continue
			elif n1 - min1 > 0:
				li.append(n1 - min1)
				n1 = n1 - min1
				min1 = 1
			else:
				break
		if len(li) > 0:
			return li
		else:
			return [0]


class Solution:

	def RopeCutting(self, a, n):
		ans = []
		l = n
		count = 1
		a.sort()
		for i in range(0, n - 1):
			if a[i] == a[i + 1]:
				count += 1
			else:
				l -= count
				ans.append(l)
				count = 1
		return ans


class Solution:

	def RopeCutting(self, arr, n):
		results = []
		arr.sort()
		current_min = arr[0]
		for i in range(n):
			if arr[i] - current_min > 0:
				results.append(n - i)
				current_min = arr[i]
		return results


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		cutt = arr[0]
		l1 = []
		for i in range(1, n):
			if arr[i] - cutt > 0:
				l1.append(n - i)
				cutt = arr[i]
		return l1


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		res = []
		cuttinglength = arr[0]
		for i in range(n):
			if arr[i] != cuttinglength:
				cuttinglength = arr[i]
				res += [n - i]
		return res


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		count = n
		answer = []
		i = 0
		while i < n - 1:
			while i < n - 1 and arr[i] == arr[i + 1]:
				count -= 1
				i += 1
			count -= 1
			if count == 0:
				if len(answer) == 0:
					return [0]
				return answer
			answer.append(count)
			i += 1
		return answer


class Solution:

	def RopeCutting(self, arr, n):
		k = []
		arr.sort()
		single_operation = 0
		min_length = arr[0]
		for i in range(1, n):
			if arr[i] - min_length > 0:
				k.append(n - i)
			min_length = arr[i]
			single_operation += 1
		if single_operation == 0:
			return 0
		return k


class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		cut = arr[0]
		result = []
		for idx in range(n):
			if arr[idx] != cut:
				cut = arr[idx]
				result += [n - idx]
		return result


class Solution:

	def RopeCutting(self, arr, n):
		ans = []
		arr.sort()
		mn = min(arr)
		for i in range(n):
			if arr[i] != mn:
				mn = arr[i]
				ans += [n - i]
		return ans


class Solution:

	def RopeCutting(self, arr, n):
		a = []
		arr = sorted(arr)
		t = arr[0]
		for i in range(n):
			if arr[i] != t:
				t = arr[i]
				a.append(n - i)
		return a


class Solution:

	def RopeCutting(self, arr, n):
		temp = list(set(arr))
		temp.sort()
		x = 0
		ans = []
		y = 0
		cnt = 0
		dic = {}
		for i in arr:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		while y < len(temp) - 1:
			cnt += dic[temp[x]]
			ans.append(n - cnt)
			x += 1
			y += 1
		return ans


class Solution:

	def RopeCutting(self, Ropes, n):
		Ropes.sort()
		singleOperation = 0
		cuttingLength = Ropes[0]
		res = []
		for i in range(1, n):
			if Ropes[i] - cuttingLength > 0:
				res.append(n - i)
				cuttingLength = Ropes[i]
				singleOperation += 1
		if singleOperation == 0:
			res.append(0)
		return res


class Solution:

	def RopeCutting(self, arr, n):
		ans = []
		arr.sort()
		flag = min(arr)
		for i in range(n):
			if arr[i] != flag:
				flag = arr[i]
				ans.append(n - i)
		return ans


class Solution:

	def RopeCutting(self, a, n):
		a.sort()
		s = []
		c = a[0]
		for i in range(1, n):
			if a[i] > c:
				s.append(n - i)
				c = a[i]
		return s


class Solution:

	def RopeCutting(self, arr, n):
		res = []
		new = [0] * n
		new[0] = 1
		prev = 0
		arr.sort()
		for i in range(1, n):
			if arr[prev] == arr[i]:
				new[i] = new[prev] + 1
			else:
				new[i] = 1
			prev = i
		i = 1
		while i < n:
			if new[i] == 1:
				res.append(n - i)
			i += 1
		return res


from collections import Counter

class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		ans = []
		i = 0
		x = n
		while i < n:
			c = 0
			while i < n - 1 and arr[i] == arr[i + 1]:
				i = i + 1
				c = c + 1
			c = c + 1
			x = x - c
			if x == 0:
				return ans
			ans.append(x)
			i = i + 1
		return ans


import heapq

class Solution:

	def RopeCutting(self, arr, n):
		d = dict()
		for i in arr:
			d[i] = d.get(i, 0) + 1
		li = list(set(arr))
		heapq.heapify(li)
		ans = []
		res = n
		for i in range(0, len(li) - 1):
			k = heapq.heappop(li)
			res = res - d[k]
			d[k] = 0
			ans.append(res)
		return ans


class Solution:

	def RopeCutting(self, arr, n):
		dic = dict()
		for i in arr:
			dic[i] = dic.get(i, 0) + 1
		s = sorted(list(set(arr)))
		l = []
		for i in s:
			l.append(n - dic[i])
			n = n - dic[i]
		return l[:-1]


from collections import Counter

class Solution:

	def RopeCutting(self, arr, n):
		arr.sort()
		sm = arr[0]
		ans = []
		for i in range(1, len(arr)):
			if arr[i] > sm:
				ans.append(len(arr) - i)
				sm = arr[i]
		return ans