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