utopian_tree.js

function utopianTree(n) {
    //A naive way to approach this is to just sum through our years
    //alternating between multiplying by 2 and adding 1
    //But there is a better way by considering that our even cycles
    //are actually the sum of 2^m for m in 0..n where n is the even
    //number of years.
    //
    //This is a special sum whose value is 2^n-1 - 1.
    //See https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2
    //Then our result can be determined in O(c) time
    const numTwoCycles = Math.floor(n * 0.5);
    const height = (1 << (numTwoCycles + 1)) - 1;
    return n % 2 == 0 ? height : height << 1;
}