you can get the problem statement from here.

nice little problem.

tree_num is the sum of distinct powers of 3 with natural exponent. we can solve this problem easily if we can realize that any natural number is sum of distinct powers of 2 with natural exponent.

one illustration that any natural number is the sum of distinct powers of 2 with natural exponent is the binary representation of natural numbers. as with natural numbers we can also represent the tree numbers in binary representation and the conversion’s also similar, instead of sum of powers of 2, it is sum of powers of 3.

https://gist.github.com/2a89c52b3bef33edb85a

PS: be careful with IO. i got tle for cin/cout with ios::sync_with_stdio(0);cin.tie(0);. so either use fast io or scanf, printf

### Like this:

Like Loading...

*Related*

Couldnot understand much. Care to explain your code, plus your logic.It is very cryptic.

LikeLike

Try to solve how to

find the sum of natural number upto n i.e (n*(n + 1)) / 2(without using the formula of-course) by using the binary representation of n;

then you can easily understand it;

how to solve the sum of first n natural numbers using binary representation; think about at each place of binary representation how many 1’s appear upto that number

for example:

take n = 10

the numbers are

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

—————– adding numbers in binary representation

3*(2**3) + 4*(2**2) + 5(2**1) + 5*(2**0)

binx = ‘1010’

All we have to do is find those coefficients.

number of one’s in 1st place = 3 which is actually int(binx[1: ]) and as there are one’s then it is implied that there are a whole set of numbers (0 – 8) we have to sum up; as they are complete in the sense number of 1’s are equal(log2(n) + 1) like wise you can continue..

as you just solved for natural numbers it is quite easy how to sum up tree numbers

reply me, If you still have any doubts..

note: in case of tree numbers the answer for 10 is

3*(3**3) + 4*(3**2) + 5*(3**1) + 5*(3**0)

LikeLike

how the coefficients are calculated?

couldnt understand it

LikeLike