Given an array of integers, sort the array (in descending order) according to count of set bits in binary representation of array elements.  
Note: For integers having same number of set bits in their binary representation, sort according to their position in the original array i.e., a stable sort.
 
Example 1:
Input: 
arr[] = {5, 2, 3, 9, 4, 6, 7, 15, 32};
Output:
15 7 5 3 9 6 2 4 32
Explanation:
The integers in their binary
representation are:
15 - 1111
7  - 0111
5  - 0101
3  - 0011
9  - 1001
6  - 0110
2  - 0010
4  - 0100
32 - 10000
hence the non-increasing sorted order is:
{15}, {7}, {5, 3, 9, 6}, {2, 4, 32}
 
Example 2:
Input: 
arr[] = {1, 2, 3, 4, 5, 6};
Output: 
3 5 6 1 2 4
Explanation:
3  - 0011
5  - 0101
6  - 0110
1  - 0001
2  - 0010
4  - 0100
hence the non-increasing sorted order is
{3, 5, 6}, {1, 2, 4}
Your Task:
You don't need to print anything, printing is done by the driver code itself. You just need to complete the function sortBySetBitCount() which takes the array arr[] and its size N as inputs and sort the array arr[] inplace. Use of extra space is prohibited.
 
Expected Time Complexity: O(N.log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def sortBySetBitCount(self, arr, n):

        # Your code goes here

Solutions:
class Solution:

	def sortBySetBitCount(self, arr, n):
		func = lambda e: bin(e).count('1')
		arr.sort(reverse=True, key=func)
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):
		arr.sort(key=lambda x: -bin(x).count('1'))
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):

		def countSet(num):
			count = 0
			while num & num - 1 > 0:
				count += 1
				num = num & num - 1
			return count
		temp = []
		for elem in arr:
			temp.append([elem, countSet(elem)])
		sortedarray = sorted(temp, key=lambda k: k[1], reverse=True)
		arr[:] = [pair[0] for pair in sortedarray]
		return arr


class Solution:

	def sortBySetBitCount(self, a, n):
		ones = {}
		for i in range(n):
			ones[i] = bin(a[i]).count('1')
		ones = sorted(ones.items(), key=lambda item: item[1], reverse=True)
		list1 = []
		for (i, v) in ones:
			list1.append(a[i])
		a[:] = list1[:]


class Solution:

	def sortBySetBitCount(self, arr, n):
		dic = {}
		for i in range(len(arr)):
			dic[i] = bin(arr[i]).count('1')
		list1 = sorted(dic.items(), key=lambda x: x[1], reverse=True)
		total = []
		for (key, value) in list1:
			total.append(arr[key])
		arr[:] = total[:]


class Solution:

	def sortBySetBitCount(self, arr, n):

		def countSet(num):
			count = 0
			x = bin(elem)[2:]
			for val in x:
				if val == '1':
					count += 1
			return count
		temp = []
		for elem in arr:
			temp.append([elem, countSet(elem)])
		sortedarray = sorted(temp, key=lambda k: k[1], reverse=True)
		arr[:] = [pair[0] for pair in sortedarray]
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):
		bit = {}
		for (i, num) in enumerate(arr):
			one = bin(num).count('1')
			bit[i] = one
		bit = sorted(bit.items(), key=lambda x: x[1], reverse=True)
		li = []
		for (i, v) in bit:
			li.append(arr[i])
		arr[:] = li[:]


class Solution:

	def sortBySetBitCount(self, arr, n):
		ans = [[] for i in range(21)]
		for i in arr:
			ans[bin(i).count('1')] += [i]
		res = []
		for i in ans[::-1]:
			if len(i) != 0:
				res += i
		arr[:] = res
		return arr


class Solution:

	def sortBySetBitCount(self, a, n):
		ones = {}
		for i in range(n):
			x = a[i]
			count = 0
			while x > 0:
				x = x & x - 1
				count += 1
			ones[i] = count
		ones = sorted(ones.items(), key=lambda item: item[1], reverse=True)
		li = []
		for i in ones:
			li.append(a[i[0]])
		a[:] = li[:]


class Solution:

	def sortBySetBitCount(self, arr, n):
		dic = {}
		for i in range(n):
			num = bin(arr[i]).count('1')
			dic[i] = num
		dic = sorted(dic.items(), key=lambda itm: itm[1], reverse=True)
		li = []
		for i in dic:
			li.append(arr[i[0]])
		arr[:] = li[:]


class Solution:

	def sortBySetBitCount(self, arr, n):
		arr.sort(key=lambda x: bin(x).count('1'), reverse=True)


class Solution:

	def sortBySetBitCount(self, arr, n):
		bits = {}
		ans = [0] * n
		for i in range(n):
			s = bin(arr[i])[2:]
			cnt = s.count('1')
			if cnt in bits:
				bits[cnt].append(arr[i])
			else:
				bits[cnt] = [arr[i]]
		j = 0
		klist = list(bits.keys())
		klist.sort(reverse=True)
		for k in klist:
			for v in bits[k]:
				arr[j] = v
				j += 1


def countSetBits(x: int):
	x = bin(x)[2:]
	return x.count('1')

class Solution:

	def sortBySetBitCount(self, arr, n):
		comp = lambda x: countSetBits(x)
		arr.sort(key=comp, reverse=True)


class Solution:

	def sortBySetBitCount(self, arr, n):
		arr.sort(key=lambda ele: bin(ele)[2:].count('1'), reverse=True)


class Solution:

	def sbcnt(self, n):
		c = 0
		while n != 0:
			if n & 1 != 0:
				c += 1
			n = n >> 1
		return c

	def sortBySetBitCount(self, arr, n):
		arr.sort(key=lambda x: self.sbcnt(x), reverse=True)


class Solution:

	def sortBySetBitCount(self, arr, n):
		d = {}
		s = set()
		for i in arr:
			count = bin(i)[2:].count('1')
			s.add(count)
			if count in d:
				d[count].append(i)
			else:
				d[count] = [i]
		t = [i for i in s]
		t.sort(reverse=True)
		ans = []
		for i in t:
			cur = d[i]
			for j in cur:
				ans.append(j)
		for i in range(n):
			arr[i] = ans[i]


class Solution:

	def sortBySetBitCount(self, arr, n):
		d = dict()
		for i in arr:
			A = bin(i).count('1')
			if A in d:
				d[A].append(i)
			else:
				d[A] = [i]
		d = sorted(d.items(), reverse=True)
		l = []
		for i in d:
			A = i[1]
			for k in A:
				l.append(k)
		for i in range(0, len(arr)):
			arr[i] = l[i]
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):
		hm = {}
		for v in arr:
			cnt = 0
			tm = v
			while v:
				if v & 1:
					cnt += 1
				v = v >> 1
			if not cnt in hm:
				hm[cnt] = []
			hm[cnt].append(tm)
		j = 0
		for i in range(32, 0, -1):
			if i in hm:
				for v in hm[i]:
					arr[j] = v
					j += 1


class Solution:

	def sortBySetBitCount(self, arr, n):
		d = {}
		maxi = 0
		mini = n
		for i in range(n):
			b = bin(arr[i]).count('1')
			if b not in d:
				d[b] = [arr[i]]
			else:
				d[b].append(arr[i])
			maxi = max(maxi, b)
			mini = min(mini, b)
		ans = []
		while maxi >= mini:
			if maxi in d:
				ans.extend(d[maxi])
			maxi -= 1
		for i in range(n):
			arr[i] = ans[i]


def func(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

class Solution:

	def sortBySetBitCount(self, arr, n):
		ans = [(i, func(i)) for i in arr]
		ans.sort(key=lambda x: x[1], reverse=True)
		for (i, j) in enumerate(ans):
			arr[i] = j[0]


class Solution:

	def sortBySetBitCount(self, arr, n):
		temp = {}
		result = []
		for val in arr:
			binval = bin(val)
			count1 = binval.count('1')
			if count1 in temp:
				temp[count1].append(val)
			else:
				temp[count1] = [val]
		maxcount = len(bin(max(arr))) - 2
		while maxcount > 0:
			if maxcount in temp:
				result.extend(temp[maxcount])
			maxcount -= 1
		arr.clear()
		for val in result:
			arr.append(val)


from collections import defaultdict

class Solution:

	def sortBySetBitCount(self, arr, n):

		def countsetbits(num):
			cnt = 0
			while num > 0:
				if num % 2 == 1:
					cnt += 1
				num = num // 2
			return cnt
		hm = defaultdict(list)
		for i in range(0, n):
			setbits = countsetbits(arr[i])
			hm[setbits].append(arr[i])
		l = 0
		i = 31
		while i > 0 and l < n:
			if i in hm:
				for ele in hm[i]:
					arr[l] = ele
					l += 1
			i -= 1


class Solution:

	def sortBySetBitCount(self, arr, n):

		def countone(t):
			count = 0
			for i in '{0:b}'.format(t):
				if i == '1':
					count += 1
			return count
		hash = {}
		for i in range(n):
			r = countone(arr[i])
			hash[r] = hash.get(r, [])
			hash[r].append(arr[i])
		res = []
		t = hash.keys()
		for i in sorted(t, reverse=True):
			for j in hash[i]:
				res.append(j)
		for i in range(n):
			arr[i] = res[i]


class Solution:

	def sortBySetBitCount(self, arr, n):
		d = {}
		for i in range(n):
			num = bin(arr[i]).count('1')
			d[i] = num
		d = sorted(d.items(), key=lambda item: item[1], reverse=True)
		l = []
		for i in d:
			l.append(arr[i[0]])
		arr[:] = l[:]


class Solution:

	def sortBySetBitCount(self, arr, n):
		arr.sort(key=lambda x: sum((c == '1' for c in bin(x))), reverse=True)


class Solution:

	def sortBySetBitCount(self, arr, n):
		for i in range(len(arr)):
			count = 0
			p = arr[i]
			while p:
				p = p & p - 1
				count += 1
			arr[i] = [count, arr[i]]
		arr.sort(key=lambda x: x[0], reverse=True)
		for i in range(len(arr)):
			arr[i] = arr[i][1]
		return arr


def countsetbits(n):
	x = bin(n)[2:]
	c = 0
	for i in x:
		if i == '1':
			c += 1
	return c

class Solution:

	def sortBySetBitCount(self, arr, n):
		arr.sort(key=countsetbits, reverse=True)


class Solution:

	def sortBySetBitCount(self, arr, n):

		def countbits(num):
			c = 0
			while num:
				rem = num % 2
				num = num // 2
				if rem:
					c += 1
			return c
		kmap = {}
		for ele in arr:
			c = countbits(ele)
			if c not in kmap:
				kmap[c] = [ele]
			else:
				kmap[c].append(ele)
		keys = list(kmap.keys())
		keys.sort(reverse=True)
		ind = 0
		for k in keys:
			eles = kmap[k]
			for ele in eles:
				arr[ind] = ele
				ind += 1


from collections import defaultdict

def countbit(n):
	c = 0
	while n != 0:
		if n % 2 != 0:
			c += 1
		n = n // 2
	return c

class Solution:

	def sortBySetBitCount(self, arr, n):
		dic = defaultdict(list)
		ans = []
		for i in arr:
			dic[countbit(i)].append(i)
		for (x, y) in dic.items():
			k = y
			k.reverse()
			for i in k:
				ans.append(i)
		arr.clear()
		ans.reverse()
		for i in ans:
			arr.append(i)


class Solution:

	def sortBySetBitCount(self, arr, n):
		h = {}
		for ele in arr:
			s = bin(ele)
			k = s.count('1')
			if k in h.keys():
				h[k].append(ele)
			else:
				h[k] = []
				h[k].append(ele)
		h = dict(sorted(h.items()))
		b = []
		v = list(h.values())
		for ele in v[::-1]:
			b += ele
		for i in range(n):
			arr[i] = b[i]


class Solution:

	def sortBySetBitCount(self, arr, n):
		sarr = [(arr[i], i) for i in range(n)]

		def countSetBits(val):
			cnt = 0
			while val:
				cnt += val % 2
				val = val // 2
			return cnt
		sarr = sorted(sarr, key=lambda val: (countSetBits(val[0]), n - val[1]), reverse=True)
		for i in range(len(arr)):
			arr[i] = sarr[i][0]


class Solution:

	def count_set_bits(self, ele):
		count = 0
		while ele > 0:
			if ele & 1:
				count += 1
			ele >>= 1
		return count

	def sortBySetBitCount(self, arr, n):
		arr[:] = [(arr[i], n - i) for i in range(n)]
		arr[:] = sorted(arr, key=lambda ele: (self.count_set_bits(ele[0]), ele[1]), reverse=True)
		arr[:] = [ele[0] for ele in arr]


class Solution:

	def sortBySetBitCount(self, arr, n):
		d = {}
		for i in arr:
			b = bin(i)[2:]
			c = b.count('1')
			if c in d:
				d[c].append(i)
			else:
				d[c] = [i]
		l = []
		t = list(d.keys())
		t.sort(reverse=True)
		for i in t:
			l = l + d[i]
		for i in range(len(l)):
			arr[i] = l[i]


class Solution:

	def sortBySetBitCount(self, arr, n):
		j = 0
		for i in arr:
			arr[j] = (i, bin(i)[2:].count('1'))
			j += 1
		arr[:] = sorted(arr, key=lambda a: -a[1])
		j = 0
		for i in arr:
			arr[j] = i[0]
			j += 1


class Solution:

	def sortBySetBitCount(self, arr, n):
		lis = []
		dic = {}
		for i in range(n):
			c = bin(arr[i])
			co = c.count('1')
			if co not in dic:
				dic[co] = [arr[i]]
				lis.append(co)
			else:
				dic[co].append(arr[i])
		lis.sort()
		res = []
		for i in lis[::-1]:
			res += dic[i]
		for i in range(n):
			arr[i] = res[i]
		return arr


import heapq

class Solution:

	def sortBySetBitCount(self, arr, n):
		q = []
		heapq.heapify(q)
		for i in range(n):
			x = bin(arr[i])[2:].replace('0', '')
			heapq.heappush(q, [-len(x), i, arr[i]])
		arr.clear()
		while q:
			arr.append(heapq.heappop(q)[2])
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):

		def bina(i):
			return bin(i).count('1')
		arr.sort(key=bina, reverse=True)
		return arr


class Solution:

	def getbits(self, a):
		s = str(bin(a))[2:]
		c = 0
		for i in s:
			if i == '1':
				c += 1
		return c

	def sortBySetBitCount(self, a, n):
		a.sort(key=self.getbits, reverse=True)


class Solution:

	def sortBySetBitCount(self, arr, n):
		for i in range(n):
			arr[i] = bin(arr[i])[2:]
		arr.sort(key=lambda x: x.count('1'), reverse=True)
		for i in range(n):
			arr[i] = int(arr[i], 2)
		return arr


class Solution:

	def counter(self, n):
		c = 0
		while n > 0:
			if n & 1 == 1:
				c += 1
			n = n >> 1
		return c

	def sortBySetBitCount(self, arr, n):
		res = sorted(arr, key=self.counter, reverse=True)
		arr[:] = res


class Solution:

	def sortBySetBitCount(self, arr, n):
		l = []
		for i in arr:
			x = bin(i)[2:]
			l.append((x.count('1'), i))
		l.sort(key=lambda x: x[0], reverse=True)
		for i in range(n):
			arr[i] = l[i][1]


class Solution:

	def sortBySetBitCount(self, a, n):
		map = {}
		maxa = 0
		for i in a:
			n = bin(i).count('1')
			if n in map:
				map[n].append(i)
			else:
				map[n] = [i]
			maxa = max(maxa, n)
		ans = []
		for i in range(maxa, -1, -1):
			if i in map:
				ans.extend(map[i])
		for i in range(0, len(ans)):
			a[i] = ans[i]
		return a


class Solution:

	def sortBySetBitCount(self, a, n):
		map = {}
		maxa = 0
		for i in a:
			n = bin(i).count('1')
			if n in map:
				map[n].append(i)
			else:
				map[n] = [i]
			maxa = max(maxa, n)
		ans = []
		for i in range(maxa, -1, -1):
			if i in map:
				ans.extend(map[i])
		for i in range(0, len(ans)):
			a[i] = ans[i]
		return a

	def getSetBitCount(self, a):
		c = 0
		while a > 0:
			if a % 2 == 1:
				c += 1
			a = int(a / 2)
		return c


def s(x):
	c = 0
	while x != 0:
		if x % 2 != 0:
			c += 1
		x = x // 2
	return c

class Solution:

	def sortBySetBitCount(self, arr, n):
		d = {}
		for i in range(n):
			d[i] = s(arr[i])
		d = sorted(d.items(), key=lambda item: item[1], reverse=True)
		l = []
		for j in d:
			l.append(arr[j[0]])
		arr[:] = l[:]
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):
		counting = []
		for i in range(32):
			counting.append([])
		for i in arr:
			string = bin(i)[2:]
			count = 0
			for j in string:
				if j == '1':
					count += 1
			counting[count].append(i)
		arr.clear()
		for list in counting[::-1]:
			for i in list:
				arr.append(i)
		return


class Solution:

	def sortBySetBitCount(self, arr, n):
		buckets = [[]]
		for item in arr:
			i = bin(item)[2:].count('1')
			while len(buckets) <= i:
				buckets.append([])
			buckets[i].append(item)
		for item in reversed(buckets):
			arr += item
		del arr[:n]


class Solution:

	def sortBySetBitCount(self, arr, n):
		hmap = {}
		for i in range(n):
			b = bin(arr[i])
			c = b.count('1')
			hmap[i] = c
		sorted_hmap = sorted(hmap.items(), key=lambda x: x[1], reverse=True)
		li = []
		for i in sorted_hmap:
			li.append(arr[i[0]])
		arr[:] = li[:]


class Solution:

	def sortBySetBitCount(self, arr, n):

		def countSetBits(n):
			count = 0
			while n:
				count += n & 1
				n >>= 1
			return count
		arr.sort(key=countSetBits, reverse=True)


class Solution:

	def NoofBits(self, A):
		count = 0
		while A:
			count += A & 1
			A >>= 1
		return count

	def sortBySetBitCount(self, arr, n):
		P = []
		for i in range(n):
			P.append([arr[i], self.NoofBits(arr[i])])
		P.sort(key=lambda x: x[1], reverse=True)
		S = []
		for i in range(len(P)):
			arr[i] = P[i][0]


class Solution:

	def sortBySetBitCount(self, arr, n):

		def count(n):
			count = 0
			while n:
				mod = n % 2
				if mod:
					count += 1
				n //= 2
			return count
		res = []
		for i in arr:
			res.append([count(i), i])
		res.sort(key=lambda x: x[0], reverse=True)
		for i in range(n):
			arr[i] = res[i][1]
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):

		def count(p):
			c = 0
			while p != 0:
				if p % 2:
					c += 1
				p = p >> 1
			return c

		def so(arr, n):
			s = []
			for i in arr:
				s.append([-1 * count(i), i])
			s.sort(key=lambda x: x[0])
			res = []
			for i in s:
				res.append(i[1])
			return res
		p = so(arr, n)
		arr[:] = p[:]


class Solution:

	def sortBySetBitCount(self, arr, n):

		def countset(n):
			c = 0
			while n:
				if n % 2 == 1:
					c += 1
				n = n >> 1
			return c
		res = []
		for i in arr:
			res.append([-1 * countset(i), i])
		res.sort(key=lambda x: x[0])
		l = []
		for i in res:
			l.append(i[1])
		arr[:] = l[:]


class Solution:

	def sortBySetBitCount(self, arr, n):
		dct = {}
		for i in range(n):
			c = 0
			temp = arr[i]
			while temp:
				c += temp & 1
				temp >>= 1
			if c not in dct:
				dct[c] = [arr[i]]
			else:
				dct[c].append(arr[i])
		ky = list(dct.keys())
		ky.sort(reverse=True)
		res = []
		for i in range(len(ky)):
			res += dct[ky[i]]
		for i in range(n):
			arr[i] = res[i]
		return arr


class Solution:

	def countBits(self, a):
		count = 0
		while a:
			if a & 1:
				count += 1
			a = a >> 1
		return count

	def sortBySetBitCount(self, arr, n):
		count = [[] for i in range(32)]
		setbitcount = 0
		for i in range(n):
			setbitcount = self.countBits(arr[i])
			count[setbitcount].append(arr[i])
		j = 0
		for i in range(31, -1, -1):
			v1 = count[i]
			for i in range(len(v1)):
				arr[j] = v1[i]
				j += 1


class Solution:

	def sortBySetBitCount(self, arr, n):
		for i in range(n):
			ele = arr[i]
			r = 0
			while ele:
				r += ele % 2
				ele = ele // 2
			arr[i] = [arr[i], r]
		arr.sort(key=lambda val: val[1], reverse=True)
		for i in range(n):
			arr[i] = arr[i][0]


import sys

class Solution:

	def sortBySetBitCount(self, arr, n):
		maxv = -sys.maxsize
		minv = sys.maxsize
		map = {}
		for i in range(n):
			ele = arr[i]
			r = 0
			while ele:
				r += ele % 2
				ele = ele // 2
			if r in map:
				li = map[r]
				li.append(arr[i])
				map[r] = li
			else:
				map[r] = [arr[i]]
			maxv = max(maxv, r)
			minv = min(minv, r)
		k = 0
		for i in range(maxv, minv - 1, -1):
			if i in map:
				for ele in map[i]:
					arr[k] = ele
					k += 1
		return arr


class Solution:

	def sortBySetBitCount(self, arr, n):

		def _cnt_set_bit(v):
			ans = 0
			while v:
				ans += 1
				v &= v - 1
			return ans
		A = [(v, i) for (i, v) in enumerate(arr)]
		A.sort(key=lambda pr: (_cnt_set_bit(pr[0]), -pr[1]), reverse=True)
		arr[:] = [v for (v, _) in A]


class Solution:

	def sortBySetBitCount(self, arr, n):
		d = {}
		for i in arr:
			t = i
			x = 0
			for j in range(31):
				x += t & 1
				t >>= 1
			if x in d:
				d[x].append(i)
			else:
				d[x] = [i]
		ans = []
		for i in range(31, -1, -1):
			if i in d:
				ans.extend(d[i])
		for i in range(n):
			arr[i] = ans[i]