{"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: 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 Output:<\/strong><\/p>\n Example2:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\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. \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 Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n <\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" 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 …<\/p>\n
\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>\nGiven number = 2<\/pre>\n
The total number of possible strings for the given number { 2 } = 3<\/pre>\n
Given number = 3<\/pre>\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
\nThe first digit is 0, and we next look for n-1 places left in the string.<\/p>\n\n
Method #1: Using Recursion (Static Input)<\/h3>\n
\n
# Create a recursive function say numberof_ways() which accepts the given number\r\n# as an argument and returns the number of possible strings with no\r\n# consecutive 1's\r\n\r\n\r\ndef numberof_ways(gvn_n):\r\n # Inside the function, check if the given number is equal to 0 using the if\r\n # conditional statement.\r\n if(gvn_n == 0):\r\n # If it is true, then return 0.\r\n return 0\r\n # Check if the given number is less than 3 using the if\r\n # conditional statement.\r\n if(gvn_n < 3):\r\n # If it is true, then return the value given number+1\r\n return gvn_n+1\r\n # Return the value numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2).\r\n # (Recursive Logic)\r\n return numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2)\r\n\r\n\r\n# Give the number as static input and store it in a variable.\r\ngvn_n = 2\r\n# Pass the given number as an argument to the numberof_ways() function and\r\n# store it in a variable.\r\nrslt = numberof_ways(gvn_n)\r\n# Print the above result.\r\nprint(\r\n \"The total number of possible strings for the given number {\", gvn_n, \"} = \", rslt)\r\n<\/pre>\n
The total number of possible strings for the given number { 2 } = 3<\/pre>\n
Method #2: Using Recursion (User Input)<\/h3>\n
\n
# Create a recursive function say numberof_ways() which accepts the given number\r\n# as an argument and returns the number of possible strings with no\r\n# consecutive 1's\r\n\r\n\r\ndef numberof_ways(gvn_n):\r\n # Inside the function, check if the given number is equal to 0 using the if\r\n # conditional statement.\r\n if(gvn_n == 0):\r\n # If it is true, then return 0.\r\n return 0\r\n # Check if the given number is less than 3 using the if\r\n # conditional statement.\r\n if(gvn_n < 3):\r\n # If it is true, then return the value given number+1\r\n return gvn_n+1\r\n # Return the value numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2).\r\n # (Recursive Logic)\r\n return numberof_ways(gvn_n-1) + numberof_ways(gvn_n-2)\r\n\r\n\r\n# Give the number as user input using the int(input()) function and store it in a variable.\r\ngvn_n = int(input(\"Enter some random number = \"))\r\n# Pass the given number as an argument to the numberof_ways() function and\r\n# store it in a variable.\r\nrslt = numberof_ways(gvn_n)\r\n# Print the above result.\r\nprint(\r\n \"The total number of possible strings for the given number {\", gvn_n, \"} = \", rslt)\r\n<\/pre>\n
Enter some random number = 3\r\nThe total number of possible strings for the given number { 3 } = 5<\/pre>\n