Tri Tiling - Implementation

Here's the solution handling multiple test cases:

function triTiling()
    while true
        n := read integer
        if n = -1 then
            break
        if n is odd then
            print 0
            continue
        if n = 0 then
            print 1
            continue
        a[0] := 1
        a[1] := 3
        for i from 2 to n/2
            a[i] := 4 * a[i-1] - a[i-2]
        print a[n/2]

Loop until $n = -1$. Return $0$ for odd $n$. Use recurrence $a[i] = 4a[i-1] - a[i-2]$ for even values.

Time complexity: $O(n)$ per test case using the linear recurrence.

Space complexity: $O(n)$ for the a array. You can reduce to $O(1)$ by keeping only the last two values.