Trail of ones

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Count binary strings of length n with no two consecutive zeros. DP.

Algorithm

1dp[i][last]: strings of length i ending with digit last. dp[i][1] = dp[i-1][0] + dp[i-1][1]. dp[i][0] = dp[i-1][1].

Common Pitfalls

•No two consecutive zeros means after a 0 must come a 1. DP with last-digit state. O(n).

Trail of ones.java

Java

// Approach: DP counting binary strings of length n with no two consecutive 1s.
// dp[i][0] = dp[i-1][0] + dp[i-1][1]; dp[i][1] = dp[i-1][0].
// Time: O(n) Space: O(1)
class Solution {
    public int countConsec(int n) {
        if (n == 2)
            return 1;
            
        int st = 1, fib1 = 0, fib2 = 1;
        for (int i = 3; i <= n; i++) {
            st = 2 * st + (fib2 + fib1);
            int temp = fib2;
            fib2 = fib1 + fib2;
            fib1 = temp;
        }

        return st;
    }
}

Was this solution helpful?