K'th bit in a binary representation with n iterations

Given a decimal number m. Consider its binary representation string and apply n iterations. In each iteration, replace the character 0 with the string 01, and 1 with 10. Find the kth (1-based indexing) character in the string after the nth iteration

Examples: 

Input: m = 5, n = 2, k = 5
Output: 0
Explanation: Binary representation of m is "101", after one iteration binary representation will be "100110", and after second iteration binary representation will be "100101101001".

Input: m = 5, n = 2, k = 1
Output: 1
Explanation: Binary representation of m is "101", after one iteration binary representation will be "100110", and after second iteration binary representation will be "100101101001".

[Naive Approach] Stimulating Each Iteration - O(2^n) Time and O(n) Space

The idea is to do as told in the problem, at every iteration we update the binary representation(i.e. update 0 to 01 and 1 to 10).

Step-By-Step Implementation:

• Change the given number into a binary and store it in string s. 
• Run loop n times. Run another loop for string length s to convert 0 to “01” and 1 to “10” and store in a temporary string s1. After completion of each iteration, assign string s1 to s. 
• Finally, return the value of the kth index in string s. 

// C++ Program to find kth character in // a binary string. #include <bits/stdc++.h> using namespace std; // Function to store binary Representation string binaryRep(int m) {  string s = "";  while (m)  {  int tmp = m % 2;  s += tmp + '0';  m = m / 2;  }  reverse(s.begin(), s.end());  return s; } // Function to find kth character int findKthChar(int n, int m, int k) {  string s = binaryRep(m);  string s1 = "";  for (int x = 0; x < n; x++)  {  for (int y = 0; y < s.length(); y++)  {  if (s[y] == '1')  s1 += "10";  else  s1 += "01";  }  // Assign s1 string in s string  s = s1;  s1 = "";  }  return s[k] - '0'; } // Driver Function int main() {  int m = 5, n = 2, k = 8;  cout << findKthChar(n, m, k);  return 0; } 

// Java Program to find kth character in a binary string. class Main {    // Function to store binary Representation  static String binaryRep(int m) {  StringBuilder s = new StringBuilder();  while (m > 0) {  int tmp = m % 2;  s.append(tmp);  m = m / 2;  }  return s.reverse().toString();  }  // Function to find kth character  static int findKthChar(int n, int m, int k) {  String s = binaryRep(m);  StringBuilder s1 = new StringBuilder();  for (int x = 0; x < n; x++) {  for (int y = 0; y < s.length(); y++) {  if (s.charAt(y) == '1')  s1.append("10");  else  s1.append("01");  }  // Assign s1 string in s string  s = s1.toString();  s1.setLength(0);  }  return s.charAt(k) - '0';  }  // Driver Function  public static void main(String[] args) {  int m = 5, n = 2, k = 8;  System.out.println(findKthChar(n, m, k));  } } 

# Python Program to find kth character in a binary string. # Function to store binary Representation def binaryRep(m): s = "" while m: tmp = m % 2 s += str(tmp) m //= 2 return s[::-1] # Function to find kth character def findKthChar(n, m, k): s = binaryRep(m) for x in range(n): s1 = "" for y in range(len(s)): if s[y] == '1': s1 += "10" else: s1 += "01" # Assign s1 string in s string s = s1 return int(s[k]) # Driver Function m = 5 n = 2 k = 8 print(findKthChar(n, m, k)) 

// C# Program to find kth character in a binary string. using System; class Program {    // Function to store binary Representation  static string BinaryRep(int m) {  string s = "";  while (m > 0) {  int tmp = m % 2;  s += tmp.ToString();  m /= 2;  }  char[] charArray = s.ToCharArray();  Array.Reverse(charArray);  return new string(charArray);  }  // Function to find kth character  static int FindKthChar(int n, int m, int k) {  string s = BinaryRep(m);  for (int x = 0; x < n; x++) {  string s1 = "";  for (int y = 0; y < s.Length; y++) {  if (s[y] == '1')  s1 += "10";  else  s1 += "01";  }  // Assign s1 string in s string  s = s1;  }  return s[k] - '0';  }  // Driver Function  static void Main() {  int m = 5, n = 2, k = 8;  Console.WriteLine(FindKthChar(n, m, k));  } } 

// JavaScript Program to find kth character in a binary string. // Function to store binary Representation function binaryRep(m) {  let s = "";  while (m > 0) {  let tmp = m % 2;  s += tmp;  m = Math.floor(m / 2);  }  return s.split('').reverse().join(''); } // Function to find kth character function findKthChar(n, m, k) {  let s = binaryRep(m);  for (let x = 0; x < n; x++) {  let s1 = "";  for (let y = 0; y < s.length; y++) {  if (s[y] === '1')  s1 += "10";  else  s1 += "01";  }    // Assign s1 string in s string  s = s1;  }  return parseInt(s[k]); } // Driver Function let m = 5, n = 2, k = 8; console.log(findKthChar(n, m, k)); 

1

[Expected Approach 1] Dividing String into Blocks - O(log(n)) Time and O(1) Space

The idea is to avoid generating the full binary string after each iteration, since its size doubles every time. Instead, we identify the original bit in m that gives rise to the k-th character after n iterations. The key observation is that the number of bit flips in a path from root to k-th character is equal to the number of set bits in offset, and parity of this count decides the final bit.

The first step will be to find which block the k-th character will be after n iterations are performed. In the n'th iteration distance between any two consecutive characters initially will always be equal to 2^n.

Consider input number m = 5

0th iteration: 101, distance = 0 
1st iteration: 10 01 10, distance = 2 
2nd iteration: 1001 0110 1001, distance = 4 
3rd iteration: 10010110 01101001 10010110, distance = 8 

We consider every bit of the input number as the start of a block and aim to determine the block number where the k-th bit will be located after n iterations. T

Finding the Block & Offset Within Block

• With each iteration, the distance between bits doubles.
• After n iterations, the bits are spaced by 2ⁿ.
• So, to find which block contains the k-th bit, we compute: {\scriptsize \text{Block number} = \left\lfloor \frac{k}{2^n} \right\rfloor}
• Example:
  If k = 5 and n = 3, then {\scriptsize \text{Block number} = \left\lfloor \frac{5}{8} \right\rfloor = 0 }

• The position of the k-th bit within the selected block is given by the remainder: {\scriptsize \text{Remaining} = k \bmod 2^n } = k % 2ⁿ

Finding k'th Bit

This offset can be thought of as a path in a binary tree formed by the repeated expansions. Each bit in the binary representation of this offset represents a decision point, a 1 indicates a flip in the bit. So, we count the number of 1s in the offset; this count gives us the number of bit flips applied to the base bit to reach the k-th position.

Finally, we use the parity of this flip count:

• If the base bit b is 0, we start with '0'. An even number of flips keeps it '0', while an odd number of flips changes it to '1'.
• If the base bit b is 1, we start with '1'. An even number of flips keeps it '1', while an odd number of flips changes it to '0'.

This flipping behavior is directly derived from the rules of expansion (0 → 01, 1 → 10), where each level toggles the bit depending on the path taken. Using this approach, we determine the final k-th bit efficiently in logarithmic time without constructing the full expanded string.

// C++ program to find k-th character after // n expansions #include <bits/stdc++.h> using namespace std; // Function to count number of set bits (Hamming weight) int countBits(int x) {  int cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt; } // Function to get k-th character after n expansions char KthCharacter(int m, int n, int k) {  int len = 1 << n;  int bit_index = (k - 1) / len;  // Get total bits in m (MSB to LSB)  int total_bits = 31 - __builtin_clz(m);  int shift = total_bits - bit_index;  int b = (m >> shift) & 1;  int offset = (k - 1) % len;  // Count set bits (parity) in offset  int ones = countBits(offset);  // Flip if parity is odd  if (b == 0) {  return (ones % 2 == 0) ? '0' : '1';  } else {  return (ones % 2 == 0) ? '1' : '0';  } } // Driver code int main() {  int m = 5, k = 5, n = 3;  cout << KthCharacter(m, n, k) << endl;  return 0; } 

// Java program to find k-th character after // n expansions class GfG {  // Function to count number of set bits (Hamming weight)  static int countBits(int x) {  int cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt;  }  // Function to get k-th character after n expansions  static char KthCharacter(int m, int n, int k) {  int len = 1 << n;  int bit_index = (k - 1) / len;  // Get total bits in m (MSB to LSB)  int total_bits = 31 - Integer.numberOfLeadingZeros(m);  int shift = total_bits - bit_index;  int b = (m >> shift) & 1;  int offset = (k - 1) % len;  // Count set bits (parity) in offset  int ones = countBits(offset);  // Flip if parity is odd  if (b == 0) {  return (ones % 2 == 0) ? '0' : '1';  } else {  return (ones % 2 == 0) ? '1' : '0';  }  }  // Driver code  public static void main(String[] args) {  int m = 5, k = 5, n = 3;  System.out.println(KthCharacter(m, n, k));  } } 

# Python program to find k-th character after # n expansions # Function to count number of set bits (Hamming weight) def countBits(x): cnt = 0 while x > 0: cnt += x & 1 x >>= 1 return cnt # Function to get k-th character after n expansions def KthCharacter(m, n, k): len_ = 1 << n bit_index = (k - 1) // len_ # Get total bits in m (MSB to LSB) total_bits = m.bit_length() - 1 shift = total_bits - bit_index b = (m >> shift) & 1 offset = (k - 1) % len_ # Count set bits (parity) in offset ones = countBits(offset) # Flip if parity is odd if b == 0: return '0' if ones % 2 == 0 else '1' else: return '1' if ones % 2 == 0 else '0' # Driver code if __name__ == "__main__": m = 5 k = 5 n = 3 print(KthCharacter(m, n, k)) 

// C# program to find k-th character after // n expansions using System; class GfG {  // Function to count number of set bits (Hamming weight)  static int countBits(int x) {  int cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt;  }  // Function to get total bits (like bit_length)  static int totalBits(int m) {  int bits = 0;  while (m > 0) {  m >>= 1;  bits++;  }  return bits;  }  // Function to get k-th character after n expansions  static char KthCharacter(int m, int n, int k) {  int len = 1 << n;  int bit_index = (k - 1) / len;  // Get total bits in m (MSB to LSB)  int total_bits = totalBits(m) - 1;  int shift = total_bits - bit_index;  int b = (m >> shift) & 1;  int offset = (k - 1) % len;  // Count set bits (parity) in offset  int ones = countBits(offset);  // Flip if parity is odd  if (b == 0) {  return (ones % 2 == 0) ? '0' : '1';  } else {  return (ones % 2 == 0) ? '1' : '0';  }  }  // Driver code  public static void Main() {  int m = 5, k = 5, n = 3;  Console.WriteLine(KthCharacter(m, n, k));  } } 

// JavaScript program to find k-th character after // n expansions // Function to count number of set bits (Hamming weight) function countBits(x) {  let cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt; } // Function to get k-th character after n expansions function KthCharacter(m, n, k) {  let len = 1 << n;  let bit_index = Math.floor((k - 1) / len);  // Get total bits in m (MSB to LSB)  let total_bits = 31 - Math.clz32(m);  let shift = total_bits - bit_index;  let b = (m >> shift) & 1;  let offset = (k - 1) % len;  // Count set bits (parity) in offset  let ones = countBits(offset);  // Flip if parity is odd  if (b === 0) {  return (ones % 2 === 0) ? '0' : '1';  } else {  return (ones % 2 === 0) ? '1' : '0';  } } // Driver code let m = 5, k = 5, n = 3; console.log(KthCharacter(m, n, k)); 

0 

[Expected Approach 2] Using Bitset - O(1) Time and O(1) Space 

The idea is to avoid generating the full binary string after each iteration, since its size doubles every time. Instead, we identify the original bit in m that gives rise to the k-th character after n iterations. The key observation is that the number of bit flips in a path from root to k-th character is equal to the number of set bits in offset, and parity of this count decides the final bit.

// C++ Code to find kth chracter after // n iterations #include <bits/stdc++.h> using namespace std; // Function to count number of set  // bits (used to compute parity) int countSetBits(int x) {  int cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt; } // Function to find the k-th character  // after n iterations char KthCharacter(int m, int n, int k) {  bitset<32> binary(m);   int totalBits = 0;  // Count number of bits in m (from MSB)  for (int i = 31; i >= 0; i--) {  if (binary[i] == 1) {  totalBits = i + 1;  break;  }  }  int blockLength = 1 << n;  int blockIndex = (k - 1) / blockLength;  int offset = (k - 1) % blockLength;  // If m has fewer bits than blockIndex, bit is 0  int root = (blockIndex < totalBits) ? binary[totalBits - blockIndex - 1] : 0;  int flips = countSetBits(offset);  // Flip if parity is odd  if (flips % 2 == 0) {  return root ? '1' : '0';  } else {  return root ? '0' : '1';  } } // Driver code int main() {  int m = 5, n = 2, k = 5;  cout << KthCharacter(m, n, k) << endl;  return 0; } 

// Java Code to find kth character after // n iterations class GfG {  // Function to count number of set   // bits (used to compute parity)  static int countSetBits(int x) {  int cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt;  }  // Function to find the k-th character   // after n iterations  static char KthCharacter(int m, int n, int k) {  int[] binary = new int[32];  for (int i = 0; i < 32; i++) {  binary[i] = (m >> i) & 1;  }  int totalBits = 0;  // Count number of bits in m (from MSB)  for (int i = 31; i >= 0; i--) {  if (binary[i] == 1) {  totalBits = i + 1;  break;  }  }  int blockLength = 1 << n;  int blockIndex = (k - 1) / blockLength;  int offset = (k - 1) % blockLength;  // If m has fewer bits than blockIndex, bit is 0  int root = (blockIndex < totalBits) ?   binary[totalBits - blockIndex - 1] : 0;  int flips = countSetBits(offset);  // Flip if parity is odd  if (flips % 2 == 0) {  return root == 1 ? '1' : '0';  } else {  return root == 1 ? '0' : '1';  }  }  public static void main(String[] args) {  int m = 5, n = 2, k = 5;  System.out.println(KthCharacter(m, n, k));  } } 

# Python Code to find kth character after # n iterations # Function to count number of set  # bits (used to compute parity) def countSetBits(x): cnt = 0 while x > 0: cnt += x & 1 x >>= 1 return cnt # Function to find the k-th character  # after n iterations def KthCharacter(m, n, k): binary = [0] * 32 for i in range(32): binary[i] = (m >> i) & 1 totalBits = 0 # Count number of bits in m (from MSB) for i in range(31, -1, -1): if binary[i] == 1: totalBits = i + 1 break blockLength = 1 << n blockIndex = (k - 1) // blockLength offset = (k - 1) % blockLength # If m has fewer bits than blockIndex, bit is 0 root = binary[totalBits - blockIndex - 1] if blockIndex < totalBits else 0 flips = countSetBits(offset) # Flip if parity is odd if flips % 2 == 0: return '1' if root else '0' else: return '0' if root else '1' if __name__ == "__main__": m, n, k = 5, 2, 5 print(KthCharacter(m, n, k)) 

// C# Code to find kth character after // n iterations using System; class GfG {  // Function to count number of set   // bits (used to compute parity)  static int countSetBits(int x) {  int cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt;  }  // Function to find the k-th character   // after n iterations  static char KthCharacter(int m, int n, int k) {  int[] binary = new int[32];  for (int i = 0; i < 32; i++) {  binary[i] = (m >> i) & 1;  }  int totalBits = 0;  // Count number of bits in m (from MSB)  for (int i = 31; i >= 0; i--) {  if (binary[i] == 1) {  totalBits = i + 1;  break;  }  }  int blockLength = 1 << n;  int blockIndex = (k - 1) / blockLength;  int offset = (k - 1) % blockLength;  // If m has fewer bits than blockIndex, bit is 0  int root = (blockIndex < totalBits) ?   binary[totalBits - blockIndex - 1] : 0;  int flips = countSetBits(offset);  // Flip if parity is odd  if (flips % 2 == 0) {  return root == 1 ? '1' : '0';  } else {  return root == 1 ? '0' : '1';  }  }  static void Main() {  int m = 5, n = 2, k = 5;  Console.WriteLine(KthCharacter(m, n, k));  } } 

// JavaScript Code to find kth character after // n iterations // Function to count number of set  // bits (used to compute parity) function countSetBits(x) {  let cnt = 0;  while (x > 0) {  cnt += x & 1;  x >>= 1;  }  return cnt; } // Function to find the k-th character  // after n iterations function KthCharacter(m, n, k) {  let binary = new Array(32).fill(0);  for (let i = 0; i < 32; i++) {  binary[i] = (m >> i) & 1;  }  let totalBits = 0;  // Count number of bits in m (from MSB)  for (let i = 31; i >= 0; i--) {  if (binary[i] === 1) {  totalBits = i + 1;  break;  }  }  let blockLength = 1 << n;  let blockIndex = Math.floor((k - 1) / blockLength);  let offset = (k - 1) % blockLength;  // If m has fewer bits than blockIndex, bit is 0  let root = (blockIndex < totalBits) ?   binary[totalBits - blockIndex - 1] : 0;  let flips = countSetBits(offset);  // Flip if parity is odd  if (flips % 2 === 0) {  return root ? '1' : '0';  } else {  return root ? '0' : '1';  } } // Driver code let m = 5, n = 2, k = 5; console.log(KthCharacter(m, n, k)); 

0