GFG Problem Of The Day

Today - 03 June 2024

Que - 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

I always encourage contributors to participate in the discussion forum for this repository.

If you have a better solution or any queries / discussions related to the Problem of the Day 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.