在n次迭代后获得的二进制字符串中找到第i个索引字符|s2

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java
Python3
C#
PHP

给定十进制数m, 将其转换为二进制字符串并应用n次迭代, 在每次迭代中0变为" 01", 而1变为" 10"。第n次迭代后, 在字符串中找到第ith(基于索引)索引字符。
例子:

Input: m = 5 i = 5 n = 3 Output: 1 Explanation In the first case m = 5, i = 5, n = 3. Initially, the string is101( 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 answerInput: m = 11 i = 6 n = 4 Output: 1

推荐：请尝试使用{IDE}首先, 在继续解决方案之前。一种天真的方法这个问题已经在以前发布。
高效算法：第一步将是查找执行N次迭代后第i个字符位于哪个块。在第n个迭代中, 任意两个连续字符之间的距离最初始终将等于2 ^ n。对于一般数字m, 块数将为ceil(log m)。如果M为3, 则字符串将分为3个块。找出第k个字符位于k /(2 ^ n)处的块号, 其中n是迭代次数。假设m = 5, 则二进制表示为101。则在第i次迭代中, 任意2个连续的标记字符之间的距离如下
第0次迭代：101, 距离= 0
第一次迭代：
1
0
0
1
1
0, 距离= 2
第2次迭代：1001
0
110
1
001, 距离= 4
第三次迭代：
1
0010110
0
1101001
1
0010110, 距离= 8
在示例中k = 5和n = 3, 所以当k为5时, Block_number将为0, 因为5 /(2 ^ 3)= 0
最初, 块号为

Original String :101 Block_number:012

无需生成整个字符串, 只需在存在第i个字符的块中进行计算即可得出答案。让这个角色成为根根= s [Block_number], 其中s是" m"的二进制表示。现在在最后一个字符串中, 找到第k个字符与程序段号的距离, 将此距离称为剩余距离。所以剩余= k％(2 ^ n)将是块中第i个字符的索引。如果剩余为0, 则根为答案。现在, 为了检查根是否是实际答案, 请使用布尔变量翻转无论我们是否需要翻转答案。遵循以下算法将在第i个索引处给出字符。

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

文章图片
下面是上述方法的实现：
C ++

// 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

// 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

# 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 % distances = [ 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 > > 1if (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.

的PHP

< ?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 ?>

输出如下：