{"id":25729,"date":"2021-12-04T09:19:48","date_gmt":"2021-12-04T03:49:48","guid":{"rendered":"https:\/\/python-programs.com\/?p=25729"},"modified":"2021-12-04T09:19:48","modified_gmt":"2021-12-04T03:49:48","slug":"python-program-to-find-number-of-possible-strings-with-no-consecutive-1s","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-to-find-number-of-possible-strings-with-no-consecutive-1s\/","title":{"rendered":"Python Program to Find Number of Possible Strings With No Consecutive 1s"},"content":{"rendered":"

Given an integer n, which represents the length of the string, or the number of bits in the final string.<\/p>\n

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

There are two possibilities for any string:
\nIf the first element is zero, the second element can be either zero or one.
\nIn the other instance, if the initial element is 1, the sole option for the next element is 0.<\/p>\n

Our task is to count the number of such possible strings that match the above-mentioned requirement.<\/p>\n

Examples:<\/strong><\/p>\n

Example1:<\/strong><\/p>\n

Input:<\/strong><\/p>\n

Given number = 2<\/pre>\n

Output:<\/strong><\/p>\n

The total number of possible strings for the given number { 2 } =  3<\/pre>\n

Example2:<\/strong><\/p>\n

Input:<\/strong><\/p>\n

Given number = 3<\/pre>\n

Output:<\/strong><\/p>\n

The total number of possible strings for the given number { 3 } = 5<\/pre>\n

Program to Find Number of Possible Strings With No Consecutive 1s in Python<\/h2>\n

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.<\/p>\n

Before going into the problem just have a glance over the recursion.<\/p>\n

The two things are as follows:<\/p>\n

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.
\nThe first digit is 0, and we next look for n-1 places left in the string.<\/p>\n

\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 n\u00a0 \u00a0<\/strong> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 number of possible strings<\/strong><\/p>\n

0\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 0<\/p>\n

1\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a02\u00a0 \u00a0(0, 1)<\/p>\n

2\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 3\u00a0 \u00a0(00, 01, 10)<\/p>\n

We will consider the two cases in all circumstances when n is bigger than 2.<\/p>\n