Hackerrank Utopian Tree (C++)

C++ :

int utopianTree(int n) {
    int height = 1;
    bool wasEven = false;

    if(n != 0){

        if(n % 2 == 0){
            n+=1;
            wasEven = true;
        }

        while(n > 0){
            //spring cycle
            if(n % 2 == 1){
                height *= 2;
            //summer cycle
            }else{
                height++;
            }
            n--;
        }
    }

    if(wasEven){
        height /= 2;
        wasEven = false;
    }

    return height;
}

Explanation:

When receiving the height of the tree, the most outer if loop checks if n is equal to 0, if it is, the default height, which is 1, is returned. Else, there is some checking of height to do.

There is a pattern to this tree. If the cycle is odd (spring cycle), the height is doubled, else, it’s summer cycle, and the height is incremented by 1.

First, check if the total number of cycles is odd or even. If the cycle is even, set wasEven to true, then add the number of cycles by 1. Why add 1 if the total number of cycles is even? This is due to using a single while loop.

Take an example where total number of cycles is 4. Cycle 0 would be height 1, cycle 1 would be height 2 (spring), cycle 2 would be height 3 (summer), cycle 3 would be height 6 (spring) and cycle 4 would be height 7 (summer). However, in the while loop, we are counting downwards (till n is lesser or equal to 0), cycle 4 is height 2 (summer!), cycle 3 is height 4 (spring!), cycle 2 is height 5 (summer!), and cycle 1 is height 10 (spring!). Since the cycle is in reverse order, the height of the tree would become wrong, so only by adding 1 and turning it into an odd cycle, the cycle would be accurate. If you use a for loop (counting from year 1 to year n), you would probably not need to add this extra 1.

The while loop finds the height of the tree, then finally, if wasEven is true, divide the final height by 2 to get the actual height.