Count Binary Strings With No Consecutive 1s | GFG Daily Practice Problem | Solution in cpp

 Question 

Given an integer N. Your task is to find the number of binary strings of length N having no
consecutive 1s.
As the number can be large, return the answer modulo 10^9+7.

Example 1:

Input:

N = 3

Output:

5

Explanation:

All the binary strings of length 3 having
no consecutive 1s are "000", "001", "101",
"100" and "010".

Example 2:

Input:
N = 2
Output:
3

Explanation:

All the binary strings of length 2 having no
consecutive 1s are "10", "00" and "01".
Your Task:
You don’t need to read input or print anything. Complete the function countStrings() which takes the
integer N as the input parameter, and returns the number of binary strings of length N with no
consecutive 1s.

Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(Height of the recursive call stack)
Constraints:
1 ≤ N ≤ 10^18

Approach

To solve this problem efficiently, we can use matrix exponentiation. Let's go step by step through the code to understand the solution.

First, we initialize the matrix F as {{1, 1}, {1, 0}} and the mod value as 10^9+7. These values are used for calculations later on.

Next, the fib() function is defined. It takes an input n and calculates the n-th Fibonacci number using matrix exponentiation. If n is 0, we simply return 0. Otherwise, we call the power() function to calculate F^(n-1), where F is the matrix defined earlier.

The power() function is a helper function that performs matrix exponentiation efficiently. If n is 0 or 1, we simply return from the function. Otherwise, we initialize matrix M as {{1, 1}, {1, 0}} and matrix ans as the identity matrix {{1, 0}, {0, 1}}.

The while loop in the power() function calculates the matrix exponentiation iteratively. It checks if n is even or odd. If n is even, we square the matrix F using the multiply() function and divide n by 2. If n is odd, we multiply the ans matrix with F and decrement n by 1. This process continues until n becomes 0.

The multiply() function performs matrix multiplication. It uses the formula x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % mod to calculate the values of x, y, z, and w in the resulting matrix F. We update the values of F accordingly and return it.

Finally, the countStrings() function takes the input N and returns the N+2-th Fibonacci number as the result. This is done by calling the fib() function.

The code is implemented in a way that handles large values of N efficiently. It takes the modulo of intermediate calculations to prevent overflow.

By following this approach, we can solve the problem in O(log(N)) time complexity due to the
efficient matrix exponentiation technique used.

Overall, this solution provides an optimized approach to count the number of binary strings of length N with no consecutive 1s

Code

#include <bits/stdc++.h>

using namespace std;

class Solution {

public:

int mod = 1e9 + 7;

int fib(long long int n) {

vector<vector<long long int>> F = {{1, 1}, {1, 0}};

if (n == 0)

return 0;

power(F, n - 1);

return F[0][0];

}

void power(vector<vector<long long int>>& F, long long int n) {

if (n == 0 || n == 1)

return;

vector<vector<long long int>> M = {{1, 1}, {1, 0}};

vector<vector<long long int>> ans = {{1, 0}, {0, 1}};

while (n > 0) {

if (n % 2 == 0) {

F = multiply(F, F);

n /= 2;

} else {

ans = multiply(ans, F);

n = n - 1;

}

}

F = ans;

}

vector<vector<long long int>> multiply(vector<vector<long long int>> F, vector<vector<long long

int>> M) {

long long int x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % mod;

long long int y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % mod;

long long int z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % mod;

long long int w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % mod;

F[0][0] = x;

F[0][1] = y;

F[1][0] = z;

F[1][1] = w;

return F;

}

int countStrings(long long int N) {

return fib(N + 2);

}

};

int main() {

int t;

cin >> t;

while (t--) {

long long int N;

cin >> N;

Solution obj;

cout << obj.countStrings(N) << endl;

}

return 0;

}