Python Program to Find Number of Possible Strings With No Consecutive 1s

Python / By

Given an integer n, which represents the length of the string, or the number of bits in the final string.

The task is to obtain a string with n bits and no consecutive 1s, which means that 11(binary) is prohibited in the string.

There are two possibilities for any string:
If the first element is zero, the second element can be either zero or one.
In the other instance, if the initial element is 1, the sole option for the next element is 0.

Our task is to count the number of such possible strings that match the above-mentioned requirement.

Examples:

Example1:

Input:

Given number = 2

Output:

The total number of possible strings for the given number { 2 } =  3

Example2:

Input:

Given number = 3

Output:

The total number of possible strings for the given number { 3 } = 5

Program to Find Number of Possible Strings With No Consecutive 1s in Python

This can be solved manually or via the recursion method. The recursion method is a superior, more efficient, and faster method of solving the problem.

Before going into the problem just have a glance over the recursion.

The two things are as follows:

The first digit is 1, then the second bit is set to 0 and we check for n-2 places left in the final string.
The first digit is 0, and we next look for n-1 places left in the string.

                                      n                          number of possible strings

0                            0

1                             2   (0, 1)

2                            3   (00, 01, 10)

We will consider the two cases in all circumstances when n is bigger than 2.

Method #1: Using Recursion (Static Input)

Approach:

  • Give the number as static input and store it in a variable.
  • Create a recursive function say numberof_ways() which accepts the given number as an argument and returns the number of possible strings with no consecutive 1’s.
  • Inside the function, check if the given number is equal to 0 using the if conditional statement.
  • If it is true, then return 0.
  • Check if the given number is less than 3 using the if conditional statement.
  • If it is true, then return the value given number+1.
  • Return the value numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2) (Recursive Logic).
  • Pass the given number as an argument to the numberof_ways() function and store it in a variable.
  • Print the above result.
  • The Exit of the Program.

Below is the implementation:

# Create a recursive function say numberof_ways() which accepts the given number
# as an argument and returns the number of possible strings with no
# consecutive 1's


def numberof_ways(gvn_n):
     # Inside the function, check if the given number is equal to 0 using the if
     # conditional statement.
    if(gvn_n == 0):
        # If it is true, then return 0.
        return 0
    # Check if the given number is less than 3 using the if
    # conditional statement.
    if(gvn_n < 3):
        # If it is true, then return the value given number+1
        return gvn_n+1
    # Return the value numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2).
    # (Recursive Logic)
    return numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2)


# Give the number as static input and store it in a variable.
gvn_n = 2
# Pass the given number as an argument to the numberof_ways() function and
# store it in a variable.
rslt = numberof_ways(gvn_n)
# Print the above result.
print(
    "The total number of possible strings for the given number {", gvn_n, "} = ", rslt)

Output:

The total number of possible strings for the given number { 2 } =  3

Method #2: Using Recursion (User Input)

Approach:

  • Give the number as user input using the int(input()) function and store it in a variable.
  • Create a recursive function say numberof_ways() which accepts the given number as an argument and returns the number of possible strings with no consecutive 1’s.
  • Inside the function, check if the given number is equal to 0 using the if conditional statement.
  • If it is true, then return 0.
  • Check if the given number is less than 3 using the if conditional statement.
  • If it is true, then return the value given number+1.
  • Return the value numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2) (Recursive Logic).
  • Pass the given number as an argument to the numberof_ways() function and store it in a variable.
  • Print the above result.
  • The Exit of the Program.

Below is the implementation:

# Create a recursive function say numberof_ways() which accepts the given number
# as an argument and returns the number of possible strings with no
# consecutive 1's


def numberof_ways(gvn_n):
     # Inside the function, check if the given number is equal to 0 using the if
     # conditional statement.
    if(gvn_n == 0):
        # If it is true, then return 0.
        return 0
    # Check if the given number is less than 3 using the if
    # conditional statement.
    if(gvn_n < 3):
        # If it is true, then return the value given number+1
        return gvn_n+1
    # Return the value numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2).
    # (Recursive Logic)
    return numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2)


# Give the number as user input using the int(input()) function and store it in a variable.
gvn_n = int(input("Enter some random number = "))
# Pass the given number as an argument to the numberof_ways() function and
# store it in a variable.
rslt = numberof_ways(gvn_n)
# Print the above result.
print(
    "The total number of possible strings for the given number {", gvn_n, "} = ", rslt)

Output:

Enter some random number = 3
The total number of possible strings for the given number { 3 } = 5