Optimization
The time complexity of the previous solution is O(n). We can enhance the efficiency of the solution to operate in O(Logn) time. When we closely examine the pattern of counting strings without consecutive 1’s, we can discern that the count is, in fact, the (n+2)th Fibonacci number for n >= 1. The Fibonacci Numbers sequence is as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, and so on.
n = 1, count = 0 = 21 - fib(3)
n = 2, count = 1 = 22 - fib(4)
n = 3, count = 3 = 23 - fib(5)
n = 4, count = 8 = 24 - fib(6)
n = 5, count = 19 = 25 - fib(7)
................
This optimization allows us to calculate the count much more efficiently using the Fibonacci sequence.
Example: This example shows the use of the above-explained approach.
// Fibonacci Series using Optimized
// Matrix Exponentiation Function
// that returns the nth Fibonacci number
function fib(n) {
// Initialize the base matrix
let F = [
[1, 1],
[1, 0],
];
// Handle the case when n is 0
if (n === 0) {
return 0;
}
// Calculate F^n using optimized
// matrix exponentiation
power(F, n - 1);
// The result is in the top-left element of F
return F[0][0];
}
// Function to multiply two matrices
function multiply(F, M) {
let x = F[0][0] * M[0][0] +
F[0][1] * M[1][0];
let y = F[0][0] * M[0][1] +
F[0][1] * M[1][1];
let z = F[1][0] * M[0][0] +
F[1][1] * M[1][0];
let w = F[1][0] * M[0][1] +
F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
// Optimized version of matrix exponentiation
function power(F, n) {
if (n <= 1) {
return;
}
let M = [
[1, 1],
[1, 0],
];
power(F, Math.floor(n / 2));
multiply(F, F);
if (n % 2 !== 0) {
multiply(F, M);
}
}
// Driver code
let n = 11;
console.log(Math.pow(2, n) - fib(n + 2));
Output
1815
Time Complexity: O(logN)
JavaScript Program to Count Strings with Consecutive 1’s
Given a number n, count the Optimized number of n-length strings with consecutive 1s in them.
Examples:
Input : n = 2
Output : 1
There are 4 strings of length 2, the
strings are 00, 01, 10 and 11. Only the
string 11 has consecutive 1's.
Input : n = 3
Output : 3
There are 8 strings of length 3, the
strings are 000, 001, 010, 011, 100,
101, 110 and 111. The strings with
consecutive 1's are 011, 110 and 111.
Input : n = 5
Output : 19
Table of Content
- Naive Approach
- Optimized Approach
- Optimization
Contact Us