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

2021年3月12日15:15:19 发表评论 358 次浏览

## 本文概述

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

## 推荐：请尝试使用{IDE}首先, 在继续解决方案之前。

1

0

0

1

1

0, 距离= 2

0

110

1

001, 距离= 4

1

0010110

0

1101001

1

0010110, 距离= 8

``````Original String :    1   0    1
Block_number    :    0   1    2``````

``````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, 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 % 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#

``````// 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 ;
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
?>``````

``1`` 