Count binary strings with k times appearing adjacent two set bits - GeeksforGeeks

Count binary strings with k times appearing adjacent two set bits - GeeksforGeeks
Given two integers n and k, count the number of binary strings of length n with k as number of times adjacent 1's appear.

Input  : n = 5, k = 2
Output : 6
Explanation:
Binary strings of length 5 in which k number of times
two adjacent set bits appear.
00111  
01110
11100
11011
10111
11101

Lets try writing the recursive function for the above problem statement:
1) n = 1, only two binary strings exist with length 1, not having any adjacent 1’s
      String 1 : “0”
      String 2 : “1”

2) For all n > 1 and all k, two cases arise
      a) Strings ending with 0 : String of length n can be created by appending 0 to all strings of length n-1 having k times two adjacent 1’s ending with both 0 and 1 (Having 0 at n’th position will not change the count of adjacent 1’s).
      b) Strings ending with 1 : String of length n can be created by appending 1 to all strings of length n-1 having k times adjacent 1’s and ending with 0 and to all strings of length n-1 having k-1 adjacent 1’s and ending with 1.

Time Complexity : O(n2)

Example: let s = 011 i.e. a string ending with 1 having adjacent count as 1. Adding 1 to it, s = 0111 increase the count of adjacent 1.

Let there be an array dp[i][j][2] where dp[i][j][0]
denotes number of binary strings with length i having
j number of two adjacent 1's and ending with 0.
Similarly dp[i][j][1] denotes the same binary strings
with length i and j adjacent 1's but ending with 1.
Then: 
    dp[1][0][0] = 1 and dp[1][0][1] = 1
    For all other i and j,
        dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]
        dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1]

Then, output dp[n][k][0] + dp[n][k][1]

int countStrings(int n, int k)

{

    // dp[i][j][0] stores count of binary

    // strings of length i with j consecutive

    // 1's and ending at 0.

    // dp[i][j][1] stores count of binary

    // strings of length i with j consecutive

    // 1's and ending at 1.

    int dp[n+1][k+1][2];

    memset(dp, 0, sizeof(dp));

    // If n = 1 and k = 0.

    dp[1][0][0] = 1;

    dp[1][0][1] = 1;

    for (int i=2; i<=n; i++)

    {

        // number of adjacent 1's can not exceed i-1

        for (int j=0; j<i; j++)

        {

            dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1];

            dp[i][j][1] = dp[i-1][j][0];

            if (j-1 >= 0)

                dp[i][j][1] += dp[i-1][j-1][1];

        }

    }

    return dp[n][k][0] + dp[n][k][1];

}

https://www.geeksforgeeks.org/number-of-binary-strings-of-length-n-with-k-adjacent-set-bits/

// Function to find the number of Bit Strings

// of length N with K adjacent set bits

int waysToKAdjacentSetBits(int dp[][MAX][2], int n, int k,

                           int currentIndex, int adjacentSetBits, int lastBit)

{

    /* Base Case when we form bit

       string of length n */

    if (currentIndex == n) {

  

        // if f(bit string) = k, count this way

        if (adjacentSetBits == k)

            return 1;

        return 0;

    }

  

    if (dp[currentIndex][adjacentSetBits][lastBit] != -1) {

  

        return dp[currentIndex][adjacentSetBits][lastBit];

    }

  

    int noOfWays = 0;

  

    /* Check if the last bit was set,

    if it was set then call for 

    next index by incrementing the

    adjacent bit count else just call

    the next index with same value of

    adjacent bit count and either set the

    bit at current index or let it remain

    unset */

  

    if (lastBit == 1) {

        // set the bit at currentIndex

        noOfWays += waysToKAdjacentSetBits(dp, n, k, currentIndex + 1, 

                                                 adjacentSetBits + 1, 1);

  

        // unset the bit at currentIndex

        noOfWays += waysToKAdjacentSetBits(dp, n, k, currentIndex + 1,

                                                    adjacentSetBits, 0);

    }

  

    else if (!lastBit) {

        noOfWays += waysToKAdjacentSetBits(dp, n, k,  currentIndex + 1, 

                                                     adjacentSetBits, 1);

  

        noOfWays += waysToKAdjacentSetBits(dp, n, k, currentIndex + 1, 

                                                   adjacentSetBits, 0);

    }

  

    dp[currentIndex][adjacentSetBits][lastBit] = noOfWays;

  

    return noOfWays;

}




https://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

Count number of binary strings without consecutive 1’s

Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s.

Examples:

Input:  N = 2
Output: 3
// The 3 strings are 00, 01, 10

Input: N = 3
Output: 5
// The 5 strings are 000, 001, 010, 100, 101

Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1. We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:

a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1] 

The base cases of above recurrence are a[1] = b[1] = 1. The total number of strings of length i is just a[i] + b[i].

Following is the implementation of above solution. In the following implementation, indexes start from 0. So a[i] represents the number of binary strings for input length i+1. Similarly, b[i] represents binary strings for input length i+1

    static  int countStrings(int n)

    {

        int a[] = new int [n];

        int b[] = new int [n];

        a[0] = b[0] = 1;

        for (int i = 1; i < n; i++)

        {

            a[i] = a[i-1] + b[i-1];

            b[i] = a[i-1];

        }

        return a[n-1] + b[n-1];

    }




If we take a closer look at the pattern, we can observe that the count is actually (n+2)’th Fibonacci number for n >= 1. The Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ….

n = 1, count = 2  = fib(3)
n = 2, count = 3  = fib(4)
n = 3, count = 5  = fib(5)
n = 4, count = 8  = fib(6)
n = 5, count = 13 = fib(7)
................

Therefore we can count the strings in O(Log n) time also using the method 5 here.

https://www.geeksforgeeks.org/count-strings-with-consecutive-1s/

Count strings with consecutive 1’s

Given a number n, count number of n length strings with consecutive 1’s in them.

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.

1) Compute number of binary strings without consecutive 1’s using the approach discussed here. Let this count be c.

2) Count of all possible binary strings with consecutive 1’s is 2^n where n is input length.

3) Total binary strings with consecutive 1 is 2^n – c.

    static int countStrings(int n)

    {

     // Count binary strings without consecutive 1's.

     // See the approach discussed on be

     // ( http://goo.gl/p8A3sW )

        int a[] = new int[n], b[] = new int[n];

        a[0] = b[0] = 1;

  

        for (int i = 1; i < n; i++) {

            a[i] = a[i - 1] + b[i - 1];

            b[i] = a[i - 1];

        }

  

       // Subtract a[n-1]+b[n-1]

 from 2^n

        return (1 << n) - a[n - 1] - b[n - 1];

    }