HackerRank: Utopian Trees

I found another fun little problem at HackerRank called Utopian trees. It is not an easy due to the input constraints. Given how small they are I am pretty sure it could be solved by bruteforce.  The problem description is

The Utopian Tree goes through 2 cycles of growth every year. Each spring, it doubles in height. Each summer, its height increases by 1 meter.

Laura plants a Utopian Tree sapling with a height of 1 meter at the onset of spring. How tall will her tree be after n growth cycles?

Given that the number of test cases is smaller than 10 and the number of cycles are less than 60, it should be pretty obvious that it can be bruteforced. However, there is also a nice analytical solution to this. 

Utopian Trees growth cycle

I had overlooked the fact that they always started out by being 1 meter high, so on the back of an enveloped I assumed that they started out being x meters tall. However, as it turns out that maede it easier to find the pattern. I basically just jotted down the development for a few cycles which can be written as

Year Spring Summer
0 x x
1 2x 2x + 1
2 2(2x +1) = 4x + 2 4x + 3
3 2(4x + 3) = 8x + 6 8x + 7
4 2(8x +7) = 16x + 14 16x + 15

where x is the starting height. Year zero is a possible input, which means that it did not have time to grow. Therefore I have just noted it as x.

If we start out by looking at the yearly cycle (after the summer growth) we can see that the factor is always 1 larger than the constant. We can also see that the grow as an exponential of 2. Which means we can express it as

Where m is the number of years it has grown which is equal to or integer division by 2 of the cycles.  Since x = 1 is always true we can simplify the solution to

Then in order to get the correct height, we must check if the cycles are odd, if that is the case we need to multiply  the height with 2 as we have gone through another spring growth.

Having this one cracked we can write the complete python code as

def utopianTree(n):
    height = 2**((n // 2) + 1) - 1
    return height if n % 2 == 0 else height*2

if __name__ == "__main__":
    t = int(input().strip())
    for a0 in range(t):
        n = int(input().strip())
        result = utopianTree(n)

Which solves the problem.

Posted by Kristian

Leave a Reply