I assume most of you are familiar with the ancient legend of the rice (but I see wikipedia suggests [wheat](https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem), for some reason) problem, but a quick recap for you: a young man asks as a compensation only `1` grain of rice for the first square, `2` grains for the second, `4` for the third, `8` for the fourth and so on, always doubling the previous.

Your task is pretty straightforward (but not necessarily easy): given an amount of grains, you need to return up to which square of the chessboard one should count in order to get at least as many.

As usual, a few examples might be way better than thousands of words from me:

```python
squares_needed(0) == 0
squares_needed(1) == 1
squares_needed(2) == 2
squares_needed(3) == 2
squares_needed(4) == 3
```

Input is always going to be valid/reasonable: ie: a non negative number; extra cookie for *not* using a loop to compute square-by-square (at least not directly) and instead trying a smarter approach [hint: some peculiar operator]; a trick converting the number might also work: impress me!

Source: codewars | Difficulty: EASY
Tags: Complete search

Mathematics

Ad-hoc

Starter code: def squares_needed(grains):
	

Solutions:
squares_needed = int.bit_length


def squares_needed(grains):
	return grains.bit_length()


def squares_needed(grains):
	if grains < 1:
		return 0
	else:
		return 1 + squares_needed(grains // 2)


from math import log2, ceil

def squares_needed(grains):
	return grains and ceil(log2(grains + 1))


def squares_needed(grains):
	sum_wheat = 0
	if grains == 0:
		return 0
	else:
		for i in range(64):
			sum_wheat += 2 ** i
			if sum_wheat >= grains:
				return i + 1


def squares_needed(grains):
	return next((i for i in range(99) if 1 << i > grains))


from math import log2

def squares_needed(grains):
	return int(log2(grains)) + 1 if grains else 0


def squares_needed(grains):
	if not grains:
		return grains
	squares = 1
	while 2 ** squares <= grains:
		squares += 1
	return squares


def squares_needed(grains):
	return 0 if grains == 0 else len(bin(grains)[2:])


import math

def squares_needed(grains):
	return 0 if grains == 0 else 1 + math.floor(math.log2(grains))


def squares_needed(grains):
	stepCount = 0
	while grains >= 1:
		grains = grains / 2
		stepCount += 1
	return stepCount


from math import log2
from math import ceil

def squares_needed(grains):
	return 0 if not grains else ceil(log2(grains + 1))


def squares_needed(grains):
	if grains == 0:
		return 0
	c = 1
	while 1:
		for i in range(1, 65):
			if c > grains:
				return i - 1
			c = c + c


import math

def squares_needed(grains):
	if grains == 0:
		return 0
	return int(math.log2(grains)) + 1


def squares_needed(grains):
	if grains == 0:
		return 0
	stop = 1
	sum = 1
	while sum < grains:
		sum = sum + 2 ** stop
		stop += 1
	return stop


def squares_needed(grains):
	n = 0
	while sum((2 ** i for i in range(n))) < grains:
		n += 1
	return n


def squares_needed(grains):
	i = 0
	while grains:
		grains >>= 1
		i += 1
	return i


def squares_needed(grains):
	if not grains:
		return 0
	else:
		return len(str(bin(grains))) - 2


def squares_needed(grains):
	import math
	try:
		x = math.log(grains)
		y = math.log(2)
		n = x / y + 1
	except ValueError:
		return 0
	return math.floor(n)


def squares_needed(g):
	y = 0
	z = 0
	for x in range(64):
		if x == 0 and g == 0:
			return x
			break
		elif x >= 1:
			if g / 2 ** x < 2 and g / 2 ** x > 1:
				y = g / 2 ** x
				return x + 1
				break
			elif g / 2 ** x <= 0.5:
				return x
				break
y = squares_needed(562949953421312)
print(y)


def squares_needed(grains):
	count = 0
	square = 1
	while square <= grains:
		count += 1
		square = square * 2
	return count


def squares_needed(grains):
	square = 0
	square_grains = 0
	while square_grains < grains:
		square += 1
		square_grains = max(square_grains * 2, 1)
	if grains == 3 or grains > 4:
		square -= 1
	return square


import math

def squares_needed(grains):
	if grains == 0:
		return 0
	a = math.ceil(math.log(grains + 1, 2))
	return a


def squares_needed(grains):
	my_dict = {}
	initial = 1
	value = 0
	for x in range(1, 65):
		my_dict[x] = initial
		initial *= 2
	listofvalues = list(my_dict.values())
	for y in listofvalues:
		if grains == None:
			return 0
			break
		elif grains == 0:
			return 0
		elif grains < y:
			continue
		else:
			value = y
	for (keys, values) in list(my_dict.items()):
		if my_dict[keys] == value:
			return keys


squares_needed = lambda n: 1 + squares_needed(n >> 1) if n else n


def squares_needed(grains):
	if grains == 0:
		return 0
	i = 0
	while (2 ** i - 1) // grains < 1:
		i += 1
	return i


squares_needed = lambda g: 0 if g == 0 else int(__import__('math').log(g, 2) + 1)


def squares_needed(grains, v=0, sum=0):
	if sum >= grains:
		return 0
	v = v * 2 if v > 0 else v + 1
	return 1 + squares_needed(grains, v, sum + v)


def squares_needed(grains):
	g = 0
	count = 0
	for i in range(0, 65):
		if g < grains:
			g = g + 2 ** i
			count += 1
		else:
			return count


def squares_needed(grains):
	grain = 1
	count_cell = 0
	while grains > 0:
		grains -= grain
		grain *= 2
		count_cell += 1
	return count_cell


def squares_needed(grains):
	grain = 1
	cell_count = 0
	while grains > 0:
		grains -= grain
		grain *= 2
		cell_count += 1
	return cell_count


def squares_needed(grains):
	import math
	a = math.log(grains + 1, 2)
	return math.ceil(a)


def squares_needed(grains, s=1, k=1):
	if grains == 0:
		return 0
	while s * 2 <= grains:
		s *= 2
		k += 1
	return k


def squares_needed(grains):
	(curr, sq) = (1, 0)
	while grains > 0:
		grains -= curr
		curr *= 2
		sq += 1
	return sq


def squares_needed(grains):
	if not grains:
		return 0
	square = 0
	base = 1
	total = 0
	while total < grains:
		total += base
		base *= 2
		square += 1
	return square


def squares_needed(grains):
	return len('{:b}'.format(grains)) if grains else 0


def squares_needed(grains):
	(sm, i) = (grains, 0)
	while sm > 0:
		sm -= 2 ** i
		i += 1
	return i


def squares_needed(grains):
	return grains and len(f'{grains:b}')


def squares_needed(grains):
	cnt = 0
	n = 1
	while n <= grains:
		n = n * 2
		cnt = cnt + 1
	return cnt


def squares_needed(grains):
	if grains < 1:
		return 0
	grains = grains // 2
	print(grains)
	return 1 + squares_needed(grains)


def squares_needed(grains):
	(square, comp) = (0, 0)
	while comp < grains:
		square += 1
		comp += 2 ** (square - 1)
	return square


def squares_needed(grains):
	if grains < 1:
		return 0
	total_wheat_rice = 0
	for i in range(64):
		total_wheat_rice += 2 ** i
		if total_wheat_rice >= grains:
			return i + 1


def squares_needed(grains):

	def sum_of_squares(sqr):
		return (2 ** sqr - 1) / (2 - 1)
	sqr = 0
	while True:
		if sum_of_squares(sqr) >= grains:
			return sqr
			break
		sqr += 1


def squares_needed(grains):
	count_of_grains = 0
	count_of_square = 0
	grains_in_square = 1
	while count_of_grains < grains:
		count_of_square += 1
		count_of_grains += grains_in_square
		grains_in_square *= 2
	return count_of_square


import math

def squares_needed(n):
	if n == 0:
		return 0
	return int(math.log(n, 2) + 1)


def squares_needed(grains):
	for i in range(0, 100):
		if 2 ** i > grains:
			return i


def squares_needed(g):
	r = 0
	while g >= 2:
		g = g >> 1
		r += 1
	return r + (g != 0)


import math

def squares_needed(grains):
	if grains == 0:
		return 0
	else:
		x = math.log(grains) // math.log(2) + 1
		return x


import math

def squares_needed(grains):
	return 0 if not grains else int(math.log(grains) / math.log(2) + 1)


import math

def squares_needed(grains):
	return grains and int(math.log(grains, 2) + 1)


def squares_needed(grains):
	if grains == 0:
		return 0
	square = 1
	grain_in_square = 1
	total_grains = 1
	while grains > total_grains:
		square += 1
		grain_in_square *= 2
		total_grains += grain_in_square
	return square


def squares_needed(grains):
	from math import ceil, log
	print(grains)
	if grains == 0:
		return 0
	else:
		return ceil(log(grains + 1, 2))


def squares_needed(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	i = 1
	cont = 1
	sum = 1
	while sum < n:
		i *= 2
		sum += i
		cont += 1
	return cont


import math

def squares_needed(grains):
	return grains if grains < 3 else math.ceil(math.log(grains + 1, 2))


from math import log

def squares_needed(n):
	if not n:
		return 0
	return int(log(n + 0.0001, 2)) + 1


def squares_needed(grains):
	mysum = 0
	sq = 0
	while mysum < grains:
		mysum += 2 ** sq
		sq += 1
	return sq


def squares_needed(grains):
	t = 0
	while grains > 0:
		t += 1
		grains = grains // 2
	return t


def squares_needed(grains):
	total = 0
	square = 0
	while grains > total:
		square += 1
		total += 2 ** (square - 1)
	return square


import math

def squares_needed(grains):
	if grains == 0:
		return 0
	if grains == 1:
		return 1
	res = math.floor(math.log(grains, 2)) + 1
	return res


def squares_needed(grains):
	if grains == 0:
		return 0
	else:
		high_square = 0
		tablet = []
		print(tablet)
		for i in range(0, 64):
			tablet.append(2 ** i)
		for i in range(0, 64):
			if sum(tablet[:i + 1]) >= grains:
				high_square = i + 1
				break
		return high_square


def squares_needed(grains):
	s = 0
	cells = 0
	grains_in_cell = 1
	while s < grains:
		s += grains_in_cell
		grains_in_cell *= 2
		cells += 1
	return cells


def squares_needed(grains):
	s = 0
	cells = 0
	gr_in_cell = 1
	while s < grains:
		s = s + gr_in_cell
		gr_in_cell *= 2
		cells += 1
	return cells


def squares_needed(grains):
	counter = 0
	if grains == 0:
		return 0
	if grains == 1:
		return 1
	for square in range(1, 64 + 1):
		while grains > 0:
			counter += 1
			grains = grains // 2
	return counter


def squares_needed(grains, b=1, c=0):
	if c == 0:
		b = 1
	else:
		b *= 2
	if grains <= 0:
		return c
	c += 1
	return squares_needed(grains - b, b, c)
	return c


def squares_needed(grains):
	n = 0
	needed = 0
	while grains > needed:
		needed += 2 ** n
		n += 1
	return n


import math

def squares_needed(grains):
	if grains == 0:
		return 0
	if grains % 2 == 0:
		needed = int(math.log2(grains)) + 1
	elif grains == 1:
		return 1
	else:
		needed = int(math.log2(grains - 1)) + 1
	return needed


def squares_needed(grains, squares=0):
	if grains == 0:
		return 0
	while grains >= 2 << squares:
		squares += 1
	return squares + 1


def squares_needed(grains):
	import math
	if grains == 0:
		return 0
	elif grains == 1:
		return 1
	n = math.log(grains + 1, 2)
	return math.ceil(n)


def squares_needed(grains):
	if grains == 0:
		return grains
	total = 0
	for i in range(0, 65):
		total += 2 ** i
		if grains <= total:
			return i + 1


def squares_needed(grains):
	if grains <= 1:
		return grains
	grain_ammount = [grains]
	while grains >= 2:
		grain_ammount.append(grains / 2)
		grains = grains / 2
	return len(grain_ammount)


def squares_needed(grains):
	ct = 0
	i = 0
	while ct < grains:
		ct += 2 ** i
		i += 1
	return i


def squares_needed(grains, step=0, cell=1):
	if grains <= 0:
		return step
	else:
		grains -= cell
		cell = cell * 2
		step += 1
		return squares_needed(grains, step, cell)


def squares_needed(grains):
	(s, r) = (0, 0)
	while grains > r:
		s += 1
		r += 2 ** (s - 1)
	return s


def squares_needed(grains):
	count = 0
	total = 1
	while total <= grains:
		a = total * 2
		total = a
		count += 1
	return count


def squares_needed(grains):
	count = 0
	print(grains)
	if grains == 0:
		return grains
	product = 1
	while grains >= 1:
		count += 1
		grains -= product
		product *= 2
	return count


def squares_needed(grains):
	chess = []
	rice = 1
	for i in range(1, 65):
		chess.append(rice)
		rice *= 2
	return max([chess.index(i) for i in chess if grains >= i]) + 1 if grains else 0


def squares_needed(grains):
	count = 0
	i = 0
	while count < grains:
		count += 2 ** i
		i += 1
	return i


from math import log, ceil

def squares_needed(grains):
	return ceil(1.4423 * log(grains) + 0.0347) if grains else 0


def squares_needed(grains):
	if grains == 0:
		return 0
	else:
		p = 1
		boxes = 1
		i = 1
		while i < grains:
			i += p * 2
			p *= 2
			boxes += 1
		return boxes