Tomya is a girl. She loves Chef Ciel very much.

Tomya like a positive integer p, and now she wants to get a receipt of Ciel's restaurant whose total price is exactly p.
The current menus of Ciel's restaurant are shown the following table.
Name of Menupriceeel flavored water1deep-fried eel bones2clear soup made with eel livers4grilled eel livers served with grated radish8savory egg custard with eel16eel fried rice (S)32eel fried rice (L)64grilled eel wrapped in cooked egg128eel curry rice256grilled eel over rice512deluxe grilled eel over rice1024eel full-course2048

Note that the i-th menu has the price 2i-1 (1 ≤ i ≤ 12).

Since Tomya is a pretty girl, she cannot eat a lot.
So please find the minimum number of menus whose total price is exactly p.
Note that if she orders the same menu twice, then it is considered as two menus are ordered. (See Explanations for details)

-----Input-----

The first line contains an integer T, the number of test cases.
Then T test cases follow.
Each test case contains an integer p.

-----Output-----

For each test case, print the minimum number of menus whose total price is exactly p.

-----Constraints-----

1 ≤ T ≤ 5

1 ≤ p ≤ 100000 (105)

There exists combinations of menus whose total price is exactly p.

-----Sample Input-----
4
10
256
255
4096

-----Sample Output-----
2
1
8
2

-----Explanations-----

In the first sample, examples of the menus whose total price is 10 are the following:

1+1+1+1+1+1+1+1+1+1 = 10 (10 menus)

1+1+1+1+1+1+1+1+2 = 10 (9 menus)

2+2+2+2+2 = 10 (5 menus)

2+4+4 = 10 (3 menus)

2+8 = 10 (2 menus)

Here the minimum number of menus is 2.

In the last sample, the optimal way is 2048+2048=4096 (2 menus).
Note that there is no menu whose price is 4096.

Difficulty: EASY
Tags: Bit manipulation

Mathematics

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
for i in range(int(input())):
	a = int(input())
	j = 11
	c = 0
	while a > 0:
		b = a // 2 ** j
		c += b
		a = a % 2 ** j
		j -= 1
	print(c)


menu = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
menu = menu[::-1]
for _ in range(int(input())):
	p = int(input())
	c = 0
	idx = 0
	while p > 0:
		if menu[idx] > p:
			idx += 1
			pass
		else:
			p -= menu[idx]
			c += 1
			idx = 0
	print(c)


t = int(input())
for i in range(t):
	p = int(input())
	c = 0
	for j in range(11, -1, -1):
		while 2 ** j <= p:
			p = p - 2 ** j
			c += 1
	print(c)


t = int(input())
while t != 0:
	n = int(input())
	res = 0
	i = 11
	ct = 0
	while n:
		res += n // 2 ** i
		n = n % 2 ** i
		i -= 1
	print(res)
	t = t - 1


for _ in range(int(input())):
	n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	p = int(input())
	c = 0
	while p >= 1:
		m = []
		for q in n:
			if p >= q:
				m.append(p - q)
		p = min(m)
		c += 1
	print(c)


t = int(input())
for i in range(t):
	p = int(input())
	ans = 0
	l = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
	for j in range(len(l)):
		while p >= l[j]:
			ans += 1
			p -= l[j]
	print(ans)


l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
for i in range(int(input())):
	p = int(input())
	m = 0
	for j in range(12, 0, -1):
		m = m + p // 2 ** (j - 1)
		p = p % 2 ** (j - 1)
	print(m)


for _ in range(int(input())):
	p = int(input())
	div = int(p / 2048)
	rem = p % 2048
	set_cnt = bin(rem)[2:].count('1')
	print(div + set_cnt)


for _ in range(int(input())):
	n = int(input())
	s = 0
	s = s + n // 2048
	n = n % 2048
	s = s + n // 1024
	n = n % 1024
	s = s + n // 512
	n = n % 512
	s = s + n // 256
	n = n % 256
	s = s + n // 128
	n = n % 128
	s = s + n // 64
	n = n % 64
	s = s + n // 32
	n = n % 32
	s = s + n // 16
	n = n % 16
	s = s + n // 8
	n = n % 8
	s = s + n // 4
	n = n % 4
	s = s + n // 2
	n = n % 2
	s = s + n // 1
	n = n % 1
	print(s)


t = int(input())
l = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for _ in range(t):
	c = 0
	n = int(input())
	i = 0
	while n:
		c += n // l[i]
		n = n % l[i]
		i = i + 1
	print(c)


def bill(p):
	sum = 0
	t = 0
	i = 0
	m = 0
	while 1:
		if sum == p:
			break
		elif sum < p:
			sum = sum + y[i]
			m = m + 1
		elif sum > p:
			sum = sum - y[i]
			i = i + 1
			m = m - 1
	return m
y = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
n = int(input())
for i in range(n):
	p = int(input())
	print(bill(p))


import math
T = int(input())
for i in range(T):
	p = int(input())
	M = 0
	for i in range(12, 0, -1):
		M = M + p // 2 ** (i - 1)
		p %= 2 ** (i - 1)
	print(M)


List = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
List = List[::-1]
test = int(input())
for i in range(test):
	number = int(input())
	res = 0
	idx = 0
	while number > 0:
		if number < List[idx]:
			idx += 1
			continue
		else:
			number -= List[idx]
			res += 1
			idx = 0
	print(res)


import math
t = int(input())
for i in range(t):
	p = int(input())
	c = 0
	while p != 0:
		j = int(math.log(p, 2))
		if j > 11:
			j = 11
		p -= pow(2, j)
		c += 1
	print(c)


l = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for _ in range(int(input())):
	n = int(input())
	c = 0
	i = 0
	while i < 12:
		if l[i] <= n and n > 0:
			c += 1
			n -= l[i]
		else:
			i += 1
	print(c)


def Check(amt):
	lst = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
	count = 0
	while amt > 0:
		for i in lst:
			if amt >= i:
				count += amt // i
				amt = amt % i
	print(count)
test = int(input())
while test:
	a = int(input())
	Check(a)
	test -= 1


T = int(input())
for _ in range(T):
	p = int(input())
	lst = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	ans = 0
	for i in range(12, 0, -1):
		ans = ans + p // 2 ** (i - 1)
		p %= 2 ** (i - 1)
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	cnt = 0
	cnt = n // 2 ** 11
	n %= 2 ** 11
	while n > 0:
		num = n % 2
		cnt += num
		n //= 2
	print(cnt)
	t -= 1


a = []
for x in range(0, 12):
	a.append(2 ** x)
for y in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		k = 0
	else:
		k = 1
	while n != 1 and n != 0:
		for x in range(11, 0, -1):
			if n == a[x]:
				k += 1
				n = 0
				break
			elif a[x] < n:
				n -= a[x]
				k += 1
				break
	print(k)


l = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for _ in range(int(input())):
	x = int(input())
	d = 0
	for i in l:
		if i <= x:
			d += x // i
			x -= x // i * i
		if x == 0:
			print(d)
			break


for i in range(int(input())):
	p = int(input())
	print(bin(p).replace('0b', '')[-11:].count('1') + (p >> 11))


l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
for i in range(int(input())):
	p = int(input())
	i = len(l) - 1
	c = 0
	while i >= 0 and p != 0:
		if l[i] > p:
			i -= 1
		else:
			p = p - l[i]
			c += 1
	print(c)


s = int(input())
b = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for _ in range(s):
	v = 0
	y = int(input())
	i = 0
	while y:
		v += y // b[i]
		y = y % b[i]
		i = i + 1
	print(v)


for i in range(int(input())):
	n = int(input())
	x = n // 2048
	y = n % 2048
	z = bin(y).count('1') + x
	print(z)


N = int(input())
for i in range(N):
	p = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
	a = int(input())
	count = 0
	for i in p:
		if a >= i:
			count = count + a // i
			a = a % i
	print(count)


import math
for _ in range(int(input())):
	P = int(input())
	menus = 0
	if P >= 2048:
		while P >= 2048:
			menus += 1
			P = P - 2048
	while P > 0:
		power = int(math.pow(2, int(math.log(P, 2))))
		menus += 1
		P -= power
	print(menus)


t = int(input())
while t > 0:
	p = int(input())
	count = 0
	anch = 0
	rem = p
	i = 12
	while i >= 1 and rem != 0:
		rem = p - anch
		if rem >= 2 ** (i - 1):
			anch += 2 ** (i - 1)
			count += 1
			continue
		i -= 1
	print(count)
	t -= 1


for _ in range(int(input())):
	p = int(input())
	a = [0] * 12
	for i in range(len(a)):
		a[i] = 2 ** i
	a.sort(reverse=True)
	c = 0
	sm = 0
	n = p
	for i in a:
		if p >= 0 and p >= i:
			t = p // i
			sm += t * i
			c += t
			p = n - sm
	print(c)


for _ in range(int(input())):
	p = int(input())
	f = []
	l = [pow(2, i) for i in range(12)]
	while p != 0:
		for i in reversed(l):
			if i <= p:
				f.append(i)
				p = p - i
				break
	print(len(f))


for i in range(int(input())):
	x = int(input())
	l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	l = l[::-1]
	b = 0
	c = 0
	while x > 0:
		if x < l[b]:
			b += 1
			continue
		else:
			x = x - l[b]
			c += 1
	print(c)


x = []
for i in range(11, -1, -1):
	x.append(2 ** i)
for _ in range(int(input())):
	n = int(input())
	count = 0
	for price in x:
		while n >= price:
			n -= price
			count += 1
	print(count)


n = int(input())
while n > 0:
	t = int(input())
	l = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
	c = 0
	if t & t - 1 == 0 and t <= 2048:
		print('1')
	else:
		for i in l:
			if t >= 0:
				if t >= i:
					c += t // i
					t = t % i
			else:
				break
		print(c)
	n = n - 1


list = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
T = int(input())
list = list[::-1]
for i in range(T):
	P = int(input())
	j = 0
	ans = 0
	while P > 0:
		if P < list[j]:
			j += 1
			continue
		else:
			P -= list[j]
			ans += 1
			j = 0
	print(ans)


t = int(input())
menu = [2 ** i for i in range(11, -1, -1)]
for i in range(t):
	p = int(input())
	n = 0
	ans = 0
	while n < 12:
		ans += p // menu[n]
		p = p % menu[n]
		if p == 0:
			break
		n += 1
	print(ans)


t = int(input())
l = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for i in range(t):
	n = int(input())
	r = 0
	while n > 0:
		for j in l:
			if n >= j:
				r += n // j
				n %= j
	print(r)


t = int(input())
numbers = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
for _ in range(t):
	p = int(input())
	count = 0
	for i in range(11, 0, -1):
		count += p // numbers[i]
		p = p % numbers[i]
	if p == 1:
		print(count + 1)
	else:
		print(count)


x = int(input())
for i in range(x):
	y = int(input())
	c = 0
	p = 11
	while y > 0:
		if y >= pow(2, p):
			y = y - pow(2, p)
			c = c + 1
		else:
			p = p - 1
	print(c)


try:
	t = int(input())
	for t in range(t):
		P = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
		n = int(input())
		count = 0
		for i in P:
			if n >= i:
				count = count + n // i
				n = n % i
		print(count)
except:
	pass


t = int(input())
while t > 0:
	n = int(input())
	c = 0
	i = 11
	while n > 0:
		if n >= 2 ** i:
			n = n - 2 ** i
			c = c + 1
		else:
			i = i - 1
	print(c)
	t = t - 1


class Solution:

	def solve(self, number):
		divisor = 2 ** 11
		ans = 0
		while number > 0:
			ans += number // divisor
			number = number % divisor
			divisor = divisor // 2
		return ans

class Driver:

	def __init__(self):
		self._solver = Solution()

	def drive(self):
		test_cases = int(input().strip())
		for _ in range(test_cases):
			number = int(input().strip())
			ans = self._solver.solve(number)
			print(ans)
Driver().drive()


t = int(input())
menu = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for i in range(t):
	p = int(input())
	n = 0
	ans = 0
	while n < 12:
		ans += p // menu[n]
		p = p % menu[n]
		if p == 0:
			break
		n += 1
	print(ans)


T = int(input())
ans = []

def fun1(p, i):
	n = int(p / 2 ** i)
	return p - n * 2 ** i

def fun2(p, i):
	n = int(p / 2 ** i)
	return n
ans = []
for x in range(T):
	p = int(input())
	sum = 0
	for y in range(11, -1, -1):
		sum = sum + fun2(p, y)
		p = fun1(p, y)
	ans.append(sum)
for z in ans:
	print(z)


def Chef(amt):
	lst = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
	count = 0
	for i in lst:
		if amt > 0:
			count = count + amt // i
			amt = amt % i
	print(count)
for _ in range(int(input())):
	n = int(input())
	Chef(n)


a = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for i in range(int(input())):
	n = int(input())
	c = 0
	for j in a:
		y = n // j
		n -= y * j
		c += y
	print(c)


A = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
T = int(input())
for t in range(T):
	p = int(input())
	t = 0
	l = 11
	while p:
		i = l
		while p < A[i]:
			i = i - 1
		p = p - A[i]
		t = t + 1
		l = i
	print(t)


for _ in range(int(input())):
	cash = int(input())
	menu = 11
	count = 0
	while cash > 0:
		if cash >= pow(2, menu):
			cash -= pow(2, menu)
			count += 1
		else:
			menu -= 1
	print(count)


t = int(input())
for _ in range(t):
	p = int(input())
	m = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
	x = 0
	for i in m:
		while p >= i:
			p -= i
			x += 1
	print(x)


tc = int(input())
for _ in range(tc):
	a = int(input())
	Menu = 0
	P = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	while a > 0:
		if a >= 2048:
			Menu += a // 2048
			a = a % 2048
		if a == 0:
			break
		for i in range(0, 12):
			if P[i] > a:
				a = a - P[i - 1]
				Menu += 1
				break
	print(Menu)


try:
	t = int(input())
	for r in range(t):
		n = int(input())
		p = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
		c = 0
		if n in p:
			print(1)
		else:
			for i in range(len(p)):
				c = c + n // p[i]
				n = n % p[i]
				if n == 0:
					break
			print(c)
except:
	pass


for tc in range(int(input())):
	p = int(input())
	t = 0
	e = 0
	while p != 0:
		if 2 ** e > p:
			t += 1
			p = p - 2 ** (e - 1)
			e = 0
		elif e == 11:
			t += 1
			p = p - 2 ** e
			e = 0
		else:
			e += 1
	print(t)


n = int(input())
for i in range(n):
	p = int(input())
	menu = 0
	if p > 2048:
		menu = p // 2048 - 1
		p = p - 2048 * menu
	while p != 0:
		if p % 2 != 0:
			menu = menu + 1
		p = p // 2
	print(menu)


t = int(input())
l = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for i in range(t):
	p = int(input())
	count = 0
	i = 0
	while i < 12 and p != 0:
		if l[i] > p:
			i += 1
		else:
			p = p - l[i]
			count += 1
	print(count)


t = int(input())
for i in range(t):
	a = int(input())
	l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	z = 0
	while a >= 1:
		m = []
		for i in l:
			if a >= i:
				m.append(a - i)
		a = min(m)
		z += 1
	print(z)


t = int(input())
i = 0
while i < t:
	n = int(input())
	c = 0
	if n > 2048:
		c = n // 2048
		n = n - c * 2048
	while n > 0:
		r = n % 2
		if r == 1:
			c += 1
		n = n // 2
	print(c)
	i += 1


l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
for _ in range(int(input())):
	p = int(input())
	items = 0
	for i in range(11, -1, -1):
		while p >= l[i]:
			items += 1
			p -= l[i]
	print(items)


for i in range(int(input())):
	n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	p = int(input())
	k = 0
	for i in range(12, 0, -1):
		k += p // 2 ** (i - 1)
		p %= 2 ** (i - 1)
	print(k)


import math
t = int(input())
for i in range(t):
	p = int(input())
	c = 0
	for i in range(11, -1, -1):
		j = 0
		while j <= 1 and p >= 2 ** i:
			c += 1
			p = p - 2 ** i
	print(c)


for i in range(int(input())):
	n = int(input())
	m_count = 0
	for i in range(11, -1, -1):
		a = 2 ** i
		while n >= a:
			n -= a
			m_count += 1
	print(m_count)


EP = int(input())
menu = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
for i in range(EP):
	PC = int(input())
	EPC = 0
	res = 0
	while EPC < 12:
		res += PC // menu[EPC]
		PC = PC % menu[EPC]
		if PC == 0:
			break
		EPC += 1
	print(res)


for t in range(int(input())):
	p = int(input())
	powers = [2 ** x for x in range(11, -1, -1)]
	c = 0
	while p > 0:
		for val in powers:
			if p >= val:
				c += p // val
				p = p % val
	print(c)


t = int(input())
l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
while t:
	n = int(input())
	if n in l:
		t -= 1
		print(1)
		continue
	i = 0
	for i in range(len(l)):
		if l[i] > n:
			break
	ans = 0
	for j in range(i, -1, -1):
		ans += n // l[j]
		if n % l[j] == 0:
			break
		n = n % l[j]
	print(ans)
	t -= 1


T = int(input())
for i in range(T):
	L = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	L = L[::-1]
	p = int(input())
	i = 0
	res = 0
	while p > 0:
		if p < L[i]:
			i += 1
		else:
			p -= L[i]
			res += 1
			i = 0
	print(res)


x = int(input())
for i in range(x):
	n = int(input())
	m = 0
	for j in range(11, -1, -1):
		while n >= 2 ** j:
			n = n - 2 ** j
			m += 1
	print(m)


for i in range(int(input())):
	lis = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
	value = int(input())
	if value in lis:
		print(1)
	else:
		res = 0
		for i in lis[::-1]:
			if i <= value:
				quotient = value // i
				value = value - i * quotient
				res += quotient
			if value == 0:
				print(res)
				break


def check(n):
	lst = [2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
	count = 0
	while n > 0:
		for i in lst:
			if n >= i:
				count += n // i
				n = n % i
	print(count)
for i in range(int(input())):
	p = int(input())
	check(p)


l = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]
t = int(input())
l = l[::-1]
for i in range(t):
	a = int(input())
	j = 0
	ans = 0
	while a > 0:
		if a < l[j]:
			j += 1
			continue
		else:
			a -= l[j]
			ans += 1
			j = 0
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	m = 0
	m = n // 2 ** 11
	n %= 2 ** 11
	while n > 0:
		num = n % 2
		m += num
		n //= 2
	print(m)
	t -= 1