Start learning free

LESSON 337 OF 409 · DYNAMIC PROGRAMMING

Binary Strings Without Consecutive Ones in C++ (Time Complexity: O(N))

Practice O(n) Read the full explanation

Given a non-negative integer N return the number of binary strings of length N without 2 consecutive ones

Example:

Input: N = 3
Output: 5
Explanation: [
    "000",
    "001",
    "010",
    "100",
    "101",
]
Notes: N <= 30
STEP 1 OF 5
    Ctrl + Enter to check

    C++ · DYNAMIC PROGRAMMING

    Binary Strings Without Consecutive Ones in C++, explained

    Understanding the Problem

    The core challenge of this problem is to generate binary strings of length N such that no two consecutive '1's appear in the string. This problem has applications in coding theory, data transmission, and error detection where certain patterns need to be avoided.

    Potential pitfalls include misunderstanding the constraints and generating strings that do not meet the criteria.

    Approach

    To solve this problem, we can use dynamic programming. The idea is to build the solution for length N based on the solutions for smaller lengths. Let's break down the approach:

    • Define two arrays, dp0 and dp1, where dp0[i] represents the number of valid strings of length i ending with '0', and dp1[i] represents the number of valid strings of length i ending with '1'.
    • Initialize the base cases: dp0[1] = 1 and dp1[1] = 1.
    • For each length from 2 to N, calculate dp0[i] and dp1[i] using the following relations:
      • dp0[i] = dp0[i-1] + dp1[i-1]
      • dp1[i] = dp0[i-1]
    • The total number of valid strings of length N is dp0[N] + dp1[N].

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Initialize two arrays dp0 and dp1 of size N+1.
    2. Set the base cases: dp0[1] = 1 and dp1[1] = 1.
    3. Iterate from 2 to N and update dp0[i] and dp1[i] using the relations mentioned above.
    4. Return the sum of dp0[N] and dp1[N].

    Code Implementation

    #include <iostream>
#include <vector>

using namespace std;

// Function to count binary strings without consecutive ones
int countBinaryStrings(int N) {
    if (N == 0) return 0;
    if (N == 1) return 2; // "0" and "1"

    // dp0[i] will store the count of binary strings of length i ending with '0'
    // dp1[i] will store the count of binary strings of length i ending with '1'
    vector<int> dp0(N + 1, 0);
    vector<int> dp1(N + 1, 0);

    // Base cases
    dp0[1] = 1; // "0"
    dp1[1] = 1; // "1"

    // Fill the dp arrays
    for (int i = 2; i <= N; ++i) {
        dp0[i] = dp0[i - 1] + dp1[i - 1]; // Append '0' to all strings of length i-1
        dp1[i] = dp0[i - 1]; // Append '1' to all strings of length i-1 ending with '0'
    }

    // Total count of binary strings of length N without consecutive ones
    return dp0[N] + dp1[N];
}

int main() {
    int N;
    cout << "Enter the length of binary strings: ";
    cin << N;
    cout << "Number of binary strings of length " << N << " without consecutive ones: " << countBinaryStrings(N) << endl;
    return 0;
}

    Complexity Analysis

    The time complexity of this approach is O(N) because we are iterating from 2 to N and performing constant-time operations in each iteration. The space complexity is also O(N) due to the storage required for the dp0 and dp1 arrays.

    Edge Cases

    Consider the following edge cases:

    • N = 0: The output should be 0 as there are no binary strings of length 0.
    • N = 1: The output should be 2 as the valid strings are "0" and "1".

    Testing

    To test the solution comprehensively, consider the following test cases:

    • N = 0: Expected output is 0.
    • N = 1: Expected output is 2.
    • N = 2: Expected output is 3 ("00", "01", "10").
    • N = 3: Expected output is 5 ("000", "001", "010", "100", "101").
    • N = 4: Expected output is 8 ("0000", "0001", "0010", "0100", "0101", "1000", "1001", "1010").

    Thinking and Problem-Solving Tips

    When approaching such problems, consider breaking down the problem into smaller subproblems and look for patterns. Dynamic programming is a powerful technique for solving problems with overlapping subproblems and optimal substructure.

    Practice solving similar problems and study different algorithms to improve your problem-solving skills.

    Conclusion

    In this blog post, we discussed how to count binary strings of length N without consecutive ones using dynamic programming. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free