The challenge
Given a positive integer n, calculate the following sum:
n + n/2 + n/4 + n/8 + ...
All elements of the sum are the results of integer division.
Example
25 => 25 + 12 + 6 + 3 + 1 = 47
The solution in Python code
Option 1:
def halving_sum(n):
total = [n]
while n>=1:
n = int(n/2)
total.append(n)
return sum(total)
Option 2:
def halving_sum(n):
s=0
while n:
s+=n ; n>>=1
return s
Option 3:
def halving_sum(n):
if n == 1:
return 1
else:
return n + halving_sum(n//2)
Test cases to validate our solution
@test.describe('Example Tests')
def example_tests():
test.assert_equals(halving_sum(25),47)
test.assert_equals(halving_sum(127),247)
