with only adds and bitwise:

return ~(~1<<(n>>1)) << n%2;

Does anyone else feel slighty confused by the wording of this problem?

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?

I have been basing my solution around cycles. No where in the problem statement does it clarify that a year is a single growth cylce. If that is the case the last line should be written:

"How tall will her tree be after N growth YEARS?"

I am I the only one tripped up by this?

Here's another O(1) approach. I searched for the sequence on the Online Encylopedia of Integer Sequences and found it at https://oeis.org/A075427

There was as closed-form solution on the page.

f(n) = 2 ^ ((n+3)/2) + ((-1)^n - 3) / 2

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int numCases = in.nextInt();
        for (int i = 0; i < numCases; i++) {
            int n = in.nextInt();
            int answer = ((int) Math.pow(2, (n + 3) / 2)) + (((int) Math.pow(-1, n)) - 3) / 2;
            System.out.println(answer);
        }
    }
}

With python3

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

Did anyone try solving it this way? The output matches perfectly but the test cases tell me that the output is wrong...any suggestions?

Code in Python3:

n = int(input())

def growthCycle(x):

if x == 0:
    h = 1
elif x % 2 == 0:
    h = 2 ** ((x/2) + 1) - 1
elif x % 2 == 1:
    h = 2 ** ((x + 3)/2) - 2
return h

for l in (0, n):

g = int(input())
res = int(growthCycle(g))
print(res)