Dado un número decimal m, conviértalo en una string binaria y aplique n iteraciones, en cada iteración 0 se convierte en «01» y 1 se convierte en «10». Encuentre el carácter de índice i (indexación basada en) en la string después de la iteración n.
Ejemplos :
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
Un enfoque ingenuo de este problema se ha discutido en la publicación anterior .
Algoritmo eficiente : el primer paso será encontrar qué bloque será el i-ésimo carácter después de realizar N iteraciones. En la n-ésima iteración, la distancia entre dos caracteres consecutivos cualesquiera inicialmente siempre será igual a 2^n. Para un número general m, el número de bloques será ceil(log m). Si M era 3, la string se divide en 3 bloques. Encuentre el número de bloque en el que se encontrará el k-ésimo carácter por k / (2^n), donde n es el número de iteraciones. Considere m=5, entonces la representación binaria es 101. Entonces la distancia entre 2 caracteres marcados consecutivos en cualquier i-ésima iteración será como sigue
0-ésima iteración: 101, distancia = 0
1-ésima iteración:1 0 0 1 1 0, distancia = 2
2.ª iteración: 1001 0 110 1 001, distancia = 4
3.ª iteración: 1 0010110 0 1101001 1 0010110, distancia = 8
En el ejemplo k = 5 y n = 3, por lo que Block_number, cuando k es 5, será 0, ya que 5 / (2^3) = 0
Inicialmente, los números de bloque serán
Original String : 1 0 1 Block_number : 0 1 2
No es necesario generar la string completa, solo calcular en el bloque en el que está presente el i-ésimo carácter dará la respuesta. Sea este carácter root root = s[Block_number] , donde s es la representación binaria de “m”. Ahora, en la string final, encuentre la distancia del k-ésimo carácter desde el número de bloque, llame a esta distancia como restante. Entonces restante = k % (2^n) será el índice del i-ésimo carácter en el bloque. Si restante es 0, la raíz será la respuesta. Ahora, para verificar si la raíz es la respuesta real, use una variable booleana que cambie si necesitamos cambiar nuestra respuesta o no. Seguir el siguiente algoritmo dará el carácter en el i-ésimo índice.
bool flip = true;
while(remaining > 1){
if( remaining is odd )
flip = !flip
remaining = remaining/2;
}
A continuación se muestra la implementación del enfoque anterior:
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
?>
Javascript
<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>
1
Complejidad de tiempo: O(log Z), donde Z es la distancia entre bits inicialmente consecutivos después de N iteraciones
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mayank2498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA