{"id":7229,"date":"2020-08-10T01:12:03","date_gmt":"2020-08-10T08:12:03","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7229"},"modified":"2020-08-10T01:36:33","modified_gmt":"2020-08-10T08:36:33","slug":"leetcode-1545-find-kth-bit-in-nth-binary-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1545-find-kth-bit-in-nth-binary-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1545. Find Kth Bit in Nth Binary String"},"content":{"rendered":"\n<p>Given two positive integers&nbsp;<code>n<\/code>&nbsp;and&nbsp;<code>k<\/code>,&nbsp;the binary string&nbsp;&nbsp;<code>S<sub>n<\/sub><\/code>&nbsp;is formed as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>S<sub>1<\/sub>&nbsp;= \"0\"<\/code><\/li><li><code>S<sub>i<\/sub>&nbsp;=&nbsp;S<sub>i-1<\/sub>&nbsp;+ \"1\" + reverse(invert(S<sub>i-1<\/sub>))<\/code>&nbsp;for&nbsp;<code>i &gt; 1<\/code><\/li><\/ul>\n\n\n\n<p>Where&nbsp;<code>+<\/code>&nbsp;denotes the concatenation operation,&nbsp;<code>reverse(x)<\/code>&nbsp;returns the reversed string&nbsp;x,&nbsp;and&nbsp;<code>invert(x)<\/code>&nbsp;inverts all the bits in&nbsp;x&nbsp;(0 changes to 1 and 1 changes to 0).<\/p>\n\n\n\n<p>For example, the first 4 strings in the above sequence are:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>S<sub>1&nbsp;<\/sub>= \"0\"<\/code><\/li><li><code>S<sub>2&nbsp;<\/sub>= \"0<strong>1<\/strong>1\"<\/code><\/li><li><code>S<sub>3&nbsp;<\/sub>= \"011<strong>1<\/strong>001\"<\/code><\/li><li><code>S<sub>4<\/sub>&nbsp;= \"0111001<strong>1<\/strong>0110001\"<\/code><\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the<\/em>&nbsp;<code>k<sup>th<\/sup><\/code>&nbsp;<em>bit<\/em>&nbsp;<em>in<\/em>&nbsp;<code>S<sub>n<\/sub><\/code>. It is guaranteed that&nbsp;<code>k<\/code>&nbsp;is valid for the given&nbsp;<code>n<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, k = 1\n<strong>Output:<\/strong> \"0\"\n<strong>Explanation: <\/strong>S<sub>3<\/sub>&nbsp;is \"<strong>0<\/strong>111001\". The first bit is \"0\".\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 4, k = 11\n<strong>Output:<\/strong> \"1\"\n<strong>Explanation: <\/strong>S<sub>4<\/sub>&nbsp;is \"0111001101<strong>1<\/strong>0001\". The 11th bit is \"1\".\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 1, k = 1\n<strong>Output:<\/strong> \"0\"\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 2, k = 3\n<strong>Output:<\/strong> \"1\"\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 20<\/code><\/li><li><code>1 &lt;= k &lt;= 2<sup>n<\/sup>&nbsp;- 1<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Brute Force \/ Simulation<\/strong><\/h2>\n\n\n\n<p>Generate the string till Sn or length &gt;= k.<\/p>\n\n\n\n<p>Time complexity: O(2^n)<br>Space complexity: O(2^n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  char findKthBit(int n, int k) {\n    string ans = \"0\";\n    for (int i = 2; i <= n &#038;&#038; ans.length() < k; ++i) {\n      string tmp(rbegin(ans), rend(ans));\n      for (char&#038; c : tmp)\n        c = '1' - c + '0';\n      ans = ans + \"1\" + tmp;      \n    }\n    return ans[k - 1];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Recursion<\/strong><\/h2>\n\n\n\n<p>All the strings have odd length of L = (1 &lt;&lt; n) - 1, <br>Let say the center m = (L + 1) \/ 2<br>if n == 1, k should be 1 and ans is \"0\".<br>Otherwise<br>  if k == m, we know it's \"1\".<br>  if k &lt; m, the answer is the same as find(n-1, K)<br>  if k > m, we are finding a flipped and mirror char in S(n-1), thus the answer is flip(find(n-1, L - k + 1)).<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  char findKthBit(int n, int k) {\n    if (n == 1) return '0';\n    int l = (1 << n) - 1;\n    if (k == (l + 1) \/ 2) return '1';\n    else if (k < (l + 1) \/ 2) \n      return findKthBit(n - 1, k);\n    else\n      return '1' - findKthBit(n - 1, l - k + 1) + '0';\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\nclass Solution {\n  public char findKthBit(int n, int k) {\n    if (n == 1) return '0';\n    int l = (1 << n) - 1;\n    if (k == (l + 1) \/ 2) return '1';\n    else if (k < (l + 1) \/ 2) \n      return findKthBit(n - 1, k);\n    else\n      return (char)('1' - findKthBit(n - 1, l - k + 1) + '0');\n  }\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python3\">\nclass Solution:\n  def findKthBit(self, n: int, k: int) -> str:\n    if n == 1: return \"0\"\n    l = (1 << n) - 1    \n    if k == (l + 1) \/ 2:\n      return \"1\"\n    elif k < (l + 1) \/ 2:\n      return self.findKthBit(n - 1, k)\n    else:\n      return str(1 - int(self.findKthBit(n - 1, l - k + 1)))\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given two positive integers&nbsp;n&nbsp;and&nbsp;k,&nbsp;the binary string&nbsp;&nbsp;Sn&nbsp;is formed as follows: S1&nbsp;= &#8220;0&#8221; Si&nbsp;=&nbsp;Si-1&nbsp;+ &#8220;1&#8221; + reverse(invert(Si-1))&nbsp;for&nbsp;i &gt; 1 Where&nbsp;+&nbsp;denotes the concatenation operation,&nbsp;reverse(x)&nbsp;returns the reversed string&nbsp;x,&nbsp;and&nbsp;invert(x)&nbsp;inverts all&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[],"class_list":["post-7229","post","type-post","status-publish","format-standard","hentry","category-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7229","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7229"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7229\/revisions"}],"predecessor-version":[{"id":7232,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7229\/revisions\/7232"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7229"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7229"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7229"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}