Categories
28°C, New York
Home Javascript How to use a bottom-up dynamic programming approach In Javascript

How to use a bottom-up dynamic programming approach In Javascript

Optimization:

This approach iterates through each length of the binary strings from 2 to ‘n’, calculating the count of strings ending with zero and one separately. Then, it updates the total count accordingly. Finally, it returns the total count of binary strings with consecutive 1’s of length ‘n’.

JavaScript 
// Function to count binary strings  
// with consecutive 1's of length 'n'

function countBinaryStringsWithConsecutiveOnes(n) {
    // Initialize variables to store counts
    let countEndingWithZero = 1;
    let countEndingWithOne = 1;
    let totalCount = 1;

    // Calculate counts for each length
    for (let i = 2; i <= n; i++) {
        let tempCountEndingWithZero = countEndingWithZero;
        let tempCountEndingWithOne = countEndingWithOne;

        // For strings ending with zero, they can be extended by either zero or one
        countEndingWithZero = tempCountEndingWithZero + tempCountEndingWithOne;

        // For strings ending with one, they can only be extended by zero
        countEndingWithOne = tempCountEndingWithZero;

        // Total count of strings of length 'i'
        totalCount = countEndingWithZero + countEndingWithOne;
    }

    // Total count of binary strings with consecutive 1's of length 'n'
    return totalCount;
}

// Driver code
console.log(countBinaryStringsWithConsecutiveOnes(11));

Output
233




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

Similar Reads

Naive Approach:

...

Optimized Approach:

We’ve created a variable called “ans,” which serves as a counter to keep track of how many strings contain two consecutive ones. Our approach involves generating all possible binary strings of a specified length using a recursive technique that involves picking and not picking of elements. Once we’ve generated these strings, we examine each one to determine if it contains two or more consecutive ones. If so, we increment the “ans” variable by 1 to keep count. In the end, we simply output the value stored in the “ans” variable, which represents the total number of strings with at least two consecutive ones....

Optimization:

To address the reverse problem of counting strings that don’t contain consecutive 1’s, we can utilize a Dynamic Programming solution, as explained in a separate solution (see here). We can leverage that solution to find the count we need by following these steps:...

Using a bottom-up dynamic programming approach:

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

Tags:
#Geeks Premier League 2023 #JavaScript-DSA #JavaScript-Program #javascript-string #Geeks Premier League #JavaScript #Web Technologies

Optimization: