Dados dos enteros, n y k. Inicialmente tenemos una secuencia que consta de un solo número 1. Necesitamos considerar series formadas después de n pasos. En cada paso, agregamos la secuencia a sí misma e insertamos el valor MEX (mínimo excluido)(>0) de la secuencia en el medio. Realice (n-1) pasos. Finalmente, encuentre el valor del k-ésimo índice de la secuencia resultante.
Ejemplo:
Input : n = 3, k = 2.
Output: Initially, we have {1}, we have to perform 2 steps.
1st step : {1, 2, 1}, since MEX of {1} is 2.
2nd step: {1, 2, 1, 3, 1, 2, 1},
since MEX of {1, 2, 1} is 3.
Value of 2nd Index = 2.
Input : n = 4, k = 8.
Output: Perform 3 steps.
After second step, we have {1, 2, 1, 3, 1, 2, 1}
3rd step: {1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3,
1, 2, 1}, since MEX = 4.
Value of 8th index = 4.
Una solución simple es generar la serie usando los pasos dados y almacenarla en una array. Finalmente, devolvemos el k-ésimo elemento de la array.
Una solución eficiente es utilizar la búsqueda binaria. Observe que el elemento medio de nuestra secuencia resultante es el mismo n. La longitud de la secuencia es 2 n – 1, porque las longitudes serán como (1, 3, 7, 15….2 n -1). Utilizamos la búsqueda binaria para resolver este problema. Como sabemos, el elemento medio de una secuencia es el número del paso (de 1) realizado en él.
De hecho, cada elemento de la secuencia es un elemento intermedio en uno u otro paso.
Comenzamos a buscar el elemento desde el paso n y comparamos el índice medio con ‘k’, si lo encontramos, devolvemos n, de lo contrario, disminuimos n en 1 y actualizamos nuestro rango de nuestra búsqueda.
repetimos este paso hasta alcanzar el índice.
Implementación:
CPP
// CPP program to fin k-th element after append
// and insert middle operations
#include <bits/stdc++.h>
using namespace std;
void findElement(int n, int k)
{
int ans = n; // Middle element of the sequence
int left = 1;
// length of the resulting sequence.
int right = pow(2, n) - 1;
while (1) {
int mid = (left + right) / 2;
if (k == mid) {
cout << ans << endl;
break;
}
// Updating the middle element of next sequence
ans--;
// Moving to the left side of the middle element.
if (k < mid)
right = mid - 1;
// Moving to the right side of the middle element.
else
left = mid + 1;
}
}
// Driver code
int main()
{
int n = 4, k = 8;
findElement(n, k);
return 0;
}
Java
// Java program to fin k-th element after append
// and insert middle operations
class GFG
{
static void findElement(int n, int k)
{
// Middle element of the sequence
int ans = n;
int left = 1;
// length of the resulting sequence.
int right = (int) (Math.pow(2, n) - 1);
while (true)
{
int mid = (left + right) / 2;
if (k == mid)
{
System.out.println(ans);
break;
}
// Updating the middle element
// of next sequence
ans--;
// Moving to the left side of
// the middle element.
if (k < mid)
{
right = mid - 1;
}
// Moving to the right side of
// the middle element.
else
{
left = mid + 1;
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 4, k = 8;
findElement(n, k);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 code to find k-th element after append # and insert middle operations import math def findElement(n , k): ans = n # Middle element of the sequence left = 1 # length of the resulting sequence. right = math.pow(2, n) - 1 while 1: mid = int((left + right) / 2) if k == mid: print(ans) break # Updating the middle element of next sequence ans-=1 # Moving to the left side of the middle element. if k < mid: right = mid - 1 # Moving to the right side of the middle element. else: left = mid + 1 # Driver code n = 4 k = 8 findElement(n, k) # This code is contributed by "Sharad_Bhardwaj".
C#
// C# program to fin k-th element after append
// and insert middle operations
using System;
class GFG
{
static void findElement(int n, int k)
{
// Middle element of the sequence
int ans = n;
int left = 1;
// length of the resulting sequence.
int right = (int) (Math.Pow(2, n) - 1);
while (true)
{
int mid = (left + right) / 2;
if (k == mid)
{
Console.WriteLine(ans);
break;
}
// Updating the middle element
// of next sequence
ans--;
// Moving to the left side of
// the middle element.
if (k < mid)
{
right = mid - 1;
}
// Moving to the right side of
// the middle element.
else
{
left = mid + 1;
}
}
}
// Driver code
public static void Main()
{
int n = 4, k = 8;
findElement(n, k);
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP program to fin k-th element
// after append and insert middle
// operations
function findElement($n, $k)
{
// Middle element of the sequence
$ans = $n;
$left = 1;
// length of the resulting sequence.
$right = pow(2, $n) - 1;
while (1)
{
$mid = ($left + $right) / 2;
if ($k ==$mid)
{
echo $ans ,"\n";
break;
}
// Updating the middle element
// of next sequence
$ans--;
// Moving to the left side of
// the middle element.
if ($k < $id)
$right = $mid - 1;
// Moving to the right side
// of the middle element.
else
$left = $mid + 1;
}
}
// Driver code
$n = 4;
$k = 8;
findElement($n, $k);
// This code is contributed by aj_36
?>
Javascript
<script>
// JavaScript program to fin k-th element after append
// and insert middle operations
function findElement(n, k)
{
// Middle element of the sequence
let ans = n;
let left = 1;
// length of the resulting sequence.
let right = (Math.pow(2, n) - 1);
while (true)
{
let mid = (left + right) / 2;
if (k == mid)
{
document.write(ans);
break;
}
// Updating the middle element
// of next sequence
ans--;
// Moving to the left side of
// the middle element.
if (k < mid)
{
right = mid - 1;
}
// Moving to the right side of
// the middle element.
else
{
left = mid + 1;
}
}
}
// Driver code
let n = 4, k = 8;
findElement(n, k);
// This code is contributed by code_hunt.
</script>
Producción:
4
Complejidad de tiempo: O (log n)
Publicación traducida automáticamente
Artículo escrito por Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA