# spoj ⟿ classical ⟿ treenum2 ⟿ The art of tree numbers

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

## 3 thoughts on “spoj ⟿ classical ⟿ treenum2 ⟿ The art of tree numbers”

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

Like

1. 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)

Like

1. how the coefficients are calculated?
couldnt understand it

Like