03. Trail of ones

The problem can be found at the following link: Question Link

My Approach

• Initialize mod to (10^9 + 7) to handle large numbers and prevent overflow.

• Initialize out to 1, which will store the number of valid sequences of ones.

• Initialize x to 0 and y to 1, representing the number of valid sequences ending in a single one or two consecutive ones respectively.

• Iterate from 3 to n:

  • Update out to (out * 2 + x + y) % mod to include new sequences formed by appending "0" or "1" to previous valid sequences.

  • Temporarily store the current value of x in z.

  • Update x to the current value of y.

  • Update y to (x + z) % mod, maintaining the count of sequences ending in two consecutive ones.

• Return the final value of out.

Time and Auxiliary Space Complexity

• Time Complexity: (O(n)), since we iterate from 3 to n.

• Auxiliary Space Complexity: (O(1)), as we use a constant amount of extra space regardless of the input size.

Code (C++)

class Solution {
public:
    int numberOfConsecutiveOnes(int n) {
        int mod = 1e9 + 7;
        long out = 1;
        int x = 0, y = 1;
        for (int i = 3; i <= n; ++i) {
            out = (out * 2 + x + y) % mod;
            int z = x;
            x = y;
            y = (x + z) % mod;
        }
        return out;
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.