{"id":27182,"date":"2018-01-03T22:11:18","date_gmt":"2018-01-03T16:41:18","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27182"},"modified":"2018-01-03T22:11:18","modified_gmt":"2018-01-03T16:41:18","slug":"java-programming-count-number-of-binary-strings-without-consecutive-1s","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-count-number-of-binary-strings-without-consecutive-1s\/","title":{"rendered":"Java Programming &#8211; Count number of binary strings without consecutive 1\u2019s"},"content":{"rendered":"<p>Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1\u2019s.<span id=\"more-129801\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>Input:  N = 2\r\nOutput: 3\r\n\/\/ The 3 strings are 00, 01, 10\r\n\r\nInput: N = 3\r\nOutput: 5\r\n\/\/ The 5 strings are 000, 001, 010, 100, 101<\/pre>\n<p>This problem can be solved using Dynamic Programming. Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1\u2019s 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:<\/p>\n<pre>a[i] = a[i - 1] + b[i - 1]\r\nb[i] = a[i - 1]<\/pre>\n<p>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].<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>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.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">class Subset_sum<br\/>{<br\/>    static  int countStrings(int n)<br\/>    {<br\/>        int a[] = new int [n];<br\/>        int b[] = new int [n];<br\/>        a[0] = b[0] = 1;<br\/>        for (int i = 1; i &lt; n; i++)<br\/>        {<br\/>            a[i] = a[i-1] + b[i-1];<br\/>            b[i] = a[i-1];<br\/>        }<br\/>        return a[n-1] + b[n-1];<br\/>    }<br\/>    \/* Driver program to test above function *\/<br\/>    public static void main (String args[])<br\/>    {<br\/>          System.out.println(countStrings(3));<br\/>    }<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>5<\/pre>\n<p>If we take a closer look at the pattern, we can observe that the count is actually (n+2)\u2019th Fibonacci number for n &gt;= 1. The Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, \u2026.<\/p>\n<pre>n = 1, count = 2  = fib(3)\r\nn = 2, count = 3  = fib(4)\r\nn = 3, count = 5  = fib(5)\r\nn = 4, count = 8  = fib(6)\r\nn = 5, count = 13 = fib(7)\r\n................<\/pre>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Java Programming &#8211; Count number of binary strings without consecutive 1\u2019s &#8211; Dynamic Programming Positive integer, count all possible distinct binary string<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,2139],"tags":[70483,72848,72840,72846,72852,72855,74715,81020,81025,72853,81024],"class_list":["post-27182","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-java","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-string-length-java","tag-string-manipulation","tag-string-meaning","tag-types-of-dynamic-programming","tag-what-is-a-string"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27182","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27182"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27182\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}