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

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

本文概述

给定十进制数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 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}首先, 在继续解决方案之前。

一种天真的方法这个问题已经在以前发布。

高效算法：第一步将是查找执行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 :    1   0    1
Block_number    :    0   1    2

无需生成整个字符串, 只需在存在第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;
}
在n次迭代后获得的二进制字符串中找到第i个索引字符|s21

下面是上述方法的实现：

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

输出如下：

1

时间复杂度：O(log Z), 其中Z是N次迭代后初始连续位之间的距离

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: