Find i’th index character in a binary string obtained after n iterations | Set 2

Given a decimal number m, convert it into a binary string and apply n iterations, in each iteration 0 becomes “01” and 1 becomes “10”. Find ith(based indexing) index character in the string after nth iteration.
Examples: 
 

Input: m = 5 i = 5 n = 3
Output: 1
Explanation
In the first case m = 5, i = 5, n = 3. 
Initially, the string is 101 ( binary equivalent of 5 )
After 1st iteration - 100110
After 2nd iteration - 100101101001
After 3rd iteration - 100101100110100110010110 
The character at index 5 is 1, so 1 is the answer
Input: m = 11 i = 6 n = 4
Output: 1

A naive approach to this problem has been discussed in the previous post. 
Efficient algorithm: The first step will be to find which block the i-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. For a general number m, the number of blocks will be ceil(log m). If M was 3, the string gets divided into 3 blocks. Find the block number in which kth character will lie by k / (2^n), where n is the number of iterations. Consider m=5, then the binary representation is 101. Then the distance between any 2 consecutive marked characters in any i'th iteration will be as follows
0th iteration: 101, distance = 0 
1st iteration: 10 01 1 0, distance = 2 
2nd iteration: 1001 0110 1001, distance = 4 
3rd iteration: 10010110 01101001 10010110, distance = 8 
In the example k = 5 and n = 3, so Block_number, when k is 5, will be 0, as 5 / (2^3) = 0
Initially, block numbers will be 
 

Original String : 1 0 1
Block_number : 0 1 2

There is no need to generate the entire string, only computing in the block in which the i-th character is present will give the answer. Let this character be root root = s[Block_number], where s is the binary representation of "m". Now in the final string, find the distance of the kth character from the block number, call this distance as remaining. So remaining = k % (2^n) will be the index of i-th character in the block. If remaining is 0, the root will be the answer. Now, in order to check whether the root is the actual answer use a boolean variable flip which whether we need to flip our answer or not. Following the below algorithm will give the character at the i-th index. 
 

bool flip = true;
while(remaining > 1){
 if( remaining is odd ) 
 flip = !flip 
 remaining = remaining/2;
}

Below is the implementation of the above approach: 
 

// C++ program to find i’th Index character  // in a binary string obtained after n iterations  #include <bits/stdc++.h>  using namespace std;  // Function to find the i-th character  void KthCharacter(int m, int n, int k)  {   // distance between two consecutive   // elements after N iterations   int distance = pow(2, n);   int Block_number = k / distance;   int remaining = k % distance;   int s[32], x = 0;   // binary representation of M   for (; m > 0; x++) {   s[x] = m % 2;   m = m / 2;   }   // kth digit will be derived from root for sure   int root = s[x - 1 - Block_number];   if (remaining == 0) {   cout << root << endl;   return;   }   // Check whether there is need to   // flip root or not   bool flip = true;   while (remaining > 1) {   if (remaining & 1) {   flip = !flip;   }   remaining = remaining >> 1;   }   if (flip) {   cout << !root << endl;   }   else {   cout << root << endl;   }  }  // Driver Code  int main()  {   int m = 5, k = 5, n = 3;   KthCharacter(m, n, k);   return 0;  }  

// Java program to find ith  // Index character in a binary // string obtained after n iterations import java.io.*; class GFG  { // Function to find // the i-th character static void KthCharacter(int m,   int n, int k) {  // distance between two   // consecutive elements  // after N iterations  int distance = (int)Math.pow(2, n);  int Block_number = k / distance;  int remaining = k % distance;  int s[] = new int[32];  int x = 0;  // binary representation of M  for (; m > 0; x++)  {  s[x] = m % 2;  m = m / 2;  }  // kth digit will be   // derived from root   // for sure  int root = s[x - 1 -   Block_number];  if (remaining == 0)   {  System.out.println(root);  return;  }  // Check whether there is   // need to flip root or not  Boolean flip = true;  while (remaining > 1)   {  if ((remaining & 1) > 0)  {  flip = !flip;  }  remaining = remaining >> 1;  }  if (flip)  {  System.out.println((root > 0)?0:1);  }  else   {  System.out.println(root);  } } // Driver Code public static void main (String[] args) {  int m = 5, k = 5, n = 3;  KthCharacter(m, n, k); } } // This code is contributed  // by anuj_67. 

# Python3 program to find  # i’th Index character in # a binary string obtained # after n iterations # Function to find  # the i-th character def KthCharacter(m, n, k): # distance between two  # consecutive elements # after N iterations distance = pow(2, n) Block_number = int(k / distance) remaining = k % distance s = [0] * 32 x = 0 # binary representation of M while(m > 0) : s[x] = m % 2 m = int(m / 2) x += 1 # kth digit will be derived # from root for sure root = s[x - 1 - Block_number] if (remaining == 0): print(root) return # Check whether there  # is need to flip root # or not flip = True while (remaining > 1): if (remaining & 1): flip = not(flip) remaining = remaining >> 1 if (flip) : print(not(root)) else : print(root) # Driver Code m = 5 k = 5 n = 3 KthCharacter(m, n, k) # This code is contributed  # by smita 

// C# program to find ith  // Index character in a  // binary string obtained // after n iterations using System; class GFG  { // Function to find // the i-th character static void KthCharacter(int m,   int n,  int k) {  // distance between two   // consecutive elements  // after N iterations  int distance = (int)Math.Pow(2, n);  int Block_number = k / distance;  int remaining = k % distance;  int []s = new int[32];  int x = 0;  // binary representation of M  for (; m > 0; x++)  {  s[x] = m % 2;  m = m / 2;  }  // kth digit will be   // derived from root   // for sure  int root = s[x - 1 -   Block_number];  if (remaining == 0)   {  Console.WriteLine(root);  return;  }  // Check whether there is   // need to flip root or not  Boolean flip = true;  while (remaining > 1)   {  if ((remaining & 1) > 0)  {  flip = !flip;  }    remaining = remaining >> 1;  }  if (flip)  {  Console.WriteLine(!(root > 0));  }  else  {  Console.WriteLine(root);  } } // Driver Code public static void Main () {  int m = 5, k = 5, n = 3;  KthCharacter(m, n, k); } } // This code is contributed  // by anuj_67. 

<script> // Javascript program to find ith  // Index character in a binary // string obtained after n iterations // Function to find // the i-th character function KthCharacter(m, n, k) {  // distance between two   // consecutive elements  // after N iterations  let distance = Math.pow(2, n);  let Block_number = Math.floor(k / distance);  let remaining = k % distance;    let s = new Array(32).fill(0);  let x = 0;    // binary representation of M  for (; m > 0; x++)  {  s[x] = m % 2;  m = Math.floor(m / 2);  }    // kth digit will be   // derived from root   // for sure  let root = s[x - 1 -   Block_number];    if (remaining == 0)   {  document.write(root);  return;  }    // Check whether there is   // need to flip root or not  let flip = true;  while (remaining > 1)   {  if ((remaining & 1) > 0)  {  flip = !flip;  }  remaining = remaining >> 1;  }    if (flip)  {  document.write((root > 0)?0:1);  }  else   {  document.write(root);  } } // driver program   let m = 5, k = 5, n = 3;  KthCharacter(m, n, k);    // This code is contributed by susmitakundugoaldanga. </script> 

<?php // PHP program to find i’th Index character // in a binary string obtained after n iterations // Function to find the i-th character function KthCharacter($m, $n, $k) { // distance between two consecutive // elements after N iterations $distance = pow(2, $n); $Block_number = intval($k / $distance); $remaining = $k % $distance; $s = array(32); $x = 0; // binary representation of M for (; $m > 0; $x++) { $s[$x] = $m % 2; $m = intval($m / 2); } // kth digit will be derived from  // root for sure $root = $s[$x - 1 - $Block_number]; if ($remaining == 0) { echo $root . "\n"; return; } // Check whether there is need to // flip root or not $flip = true; while ($remaining > 1) { if ($remaining & 1) { $flip = !$flip; } $remaining = $remaining >> 1; } if ($flip) { echo !$root . "\n"; } else { echo $root . "\n"; } } // Driver Code $m = 5; $k = 5; $n = 3; KthCharacter($m, $n, $k); // This code is contributed by ita_c ?> 

1

Time Complexity: O(log Z), where Z is the distance between initially consecutive bits after N iterations
Auxiliary Space: O(1) 

Approach 2: Bitset Approach

#include <bitset> #include <iostream> using namespace std; // Function to find the i-th character void KthCharacter(int m, int n, int k) {  bitset<32> binary(m); // binary representation of M  int distance  = 1 << n; // Distance between two consecutive  // elements after N iterations  int blockNumber = k / distance;  int remaining = k % distance;  int root = binary[n - blockNumber  - 1]; // Get the kth digit from root  if (remaining == 0) {  cout << root << endl;  return;  }  bool flip = false;  while (remaining > 1) {  flip = !flip;  remaining = remaining >> 1;  }  if (flip) {  cout << !root << endl;  }  else {  cout << root << endl;  } } int main() {  int m = 5, k = 5, n = 3;  KthCharacter(m, n, k);  return 0; } 

/*package whatever //do not write package name here */ import java.io.*; import java.util.BitSet; public class Gfg {  // Function to find the i-th character  static void KthCharacter(int m, int n, int k) {  BitSet binary = BitSet.valueOf(new long[] { m }); // Binary representation of M  int distance = 1 << n; // Distance between two consecutive elements after N iterations  int blockNumber = k / distance;  int remaining = k % distance;  int root = binary.get(n - blockNumber - 1) ? 1 : 0; // Get the kth digit from root  if (remaining == 0) {  System.out.println(root);  return;  }  boolean flip = false;  while (remaining > 1) {  flip = !flip;  remaining = remaining >> 1;  }  if (flip) {  System.out.println(root == 0 ? 1 : 0);  } else {  System.out.println(root);  }  }  public static void main(String[] args) {  int m = 5, k = 5, n = 3;  KthCharacter(m, n, k);  } } // code is contributed by shinjanpatra 

def KthCharacter(m, n, k): binary = format(m, '0' + str(n) + 'b') # Binary representation of M distance = 1 << n # Distance between two consecutive elements after N iterations blockNumber = k // distance remaining = k % distance root = int(binary[n - blockNumber - 1]) # Get the kth digit from root if remaining == 0: print(root) return flip = False while remaining > 1: flip = not flip remaining = remaining >> 1 if flip: print(int(not root)) else: print(root) if __name__ == "__main__": m = 5 k = 5 n = 3 KthCharacter(m, n, k) # This code is contributed by shivamgupta310570 

using System; using System.Collections; class KthCharacterProgram {  // Function to find the i-th character  static void KthCharacter(int m, int n, int k)  {  // Binary representation of M  BitArray binary  = new BitArray(BitConverter.GetBytes(m));  // Distance between two consecutive elements after N  // iterations  int distance = 1 << n;  // Block number calculation  int blockNumber = k / distance;  // Remaining calculation  int remaining = k % distance;  // Get the kth digit from root  int root = binary[n - blockNumber - 1] ? 1 : 0;  if (remaining == 0) {  Console.WriteLine(root);  return;  }  bool flip = false;  while (remaining > 1) {  flip = !flip;  remaining = remaining >> 1;  }  // Output the result based on flipping  Console.WriteLine(flip ? (root ^ 1) : root);  }  static void Main()  {  int m = 5, k = 5, n = 3;  KthCharacter(m, n, k);  } } 

// Function to find the i-th character function KthCharacter(m, n, k) {  // Convert m to its binary representation  let binary = m.toString(2);    // Calculate the distance between two consecutive elements after N iterations  let distance = 1 << n;    // Calculate the block number and remaining value  let blockNumber = Math.floor(k / distance);  let remaining = k % distance;    // Get the kth digit from the binary representation  let root = binary[n - blockNumber - 1];    if (remaining === 0) {  console.log(root);  return;  }    let flip = false;  while (remaining > 1) {  flip = !flip;  remaining = remaining >> 1;  }    if (flip) {  console.log(root === '0' ? '1' : '0');  } else {  console.log(root);  } } // Main function function main() {  let m = 5, k = 5, n = 3;  KthCharacter(m, n, k); } main(); 

1

Time Complexity:  O(1),  since the number of iterations and the size of the bitset (32 in this case) are constant.
Auxiliary Space:  O(1),  since the bitset size is constant and does not depend on the input values.