在经过n次迭代后生成的二进制字符串中查找第i个索引位置的字符 | 第二部分

给定一个十进制数 m，我们将其转换为二进制字符串并应用 n 次迭代。在每次迭代中，0 变为 "01"，1 变为 "10"。我们的目标是在第 n 次迭代后找到该字符串中第 i 个（基于索引）字符。

示例：

输入：m = 5 i = 5 n = 3
输出：1
****解释****
在第一种情况下 m = 5, i = 5, n = 3。
初始时，字符串为  101  （5的二进制等价形式）
第1次迭代后 -   100110
第2次迭代后 - 100101101001
第3次迭代后 -   100101100110100110010110 
索引5处的字符是1，所以答案是1

输入：m = 11 i = 6 n = 4
输出：1

推荐：请在转到解决方案之前先在 {IDE} 上尝试您的方法。

在这个问题上，一种朴素方法已在上一篇文章中进行了讨论。

高效算法：第一步将是确定第 N 次迭代完成后第 i 个字符将位于哪个块中。在第 n 次迭代中，初始状态下任意两个连续字符之间的距离将始终等于 2^n。对于一般数字 m，块的数量将是 ceil(log m)。如果 M 是 3，字符串将被分为 3 个块。我们可以通过 k / (2^n) 来计算第 k 个字符所在的块号，其中 n 是迭代次数。以 m=5 为例，其二进制表示是 101。那么在任意第 i 次迭代中，任意两个连续标记字符之间的距离如下所示：

0th 迭代：101, distance = 0

1st 迭代：10 01 1 0, distance = 2

2nd 迭代：1001 0110 1001, distance = 4

3rd 迭代：10010110 01101001 10010110, distance = 8

在这个示例中，k = 5 且 n = 3，所以当 k 为 5 时，块号为 0，因为 5 / (2^3) = 0。

最初，块号将是：

原始字符串：    1   0    1
块号    ：    0   1    2

我们不需要生成整个字符串，只需要计算第 i 个字符所在的块就可以得出答案。设这个字符为根节点 root = s[Block_number]，其中 s 是 "m" 的二进制表示。现在，在最终字符串中，计算第 k 个字符距离块号的距离，我们将这个距离称为 "remaining"。所以 remaining = k % (2^n) 将是该块中第 i 个字符的索引。如果 remaining 为 0，则 root 就是答案。现在，为了检查 root 是否是真正需要的答案，我们使用一个布尔变量 flip，它表示我们需要是否需要对答案进行翻转（取反）。遵循下面的算法将得出第 i 个索引处的字符。

bool flip = true;
while(remaining > 1){
   if( remaining 是奇数 ) 
        flip = !flip    
   remaining = remaining/2;
}

!image

下面是上述方法的实现：

C++


CODEBLOCK_fa5f359b


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);