Dados dos números N y K , la tarea es encontrar el índice del K-ésimo conjunto de bits en el número de la derecha.
Nota : La indexación en la representación binaria comienza desde 0 desde la derecha. Por ejemplo, en el número binario «000011», el primer bit establecido está en el índice 0 desde la derecha y el segundo bit establecido está en el índice 1 desde la derecha.
Ejemplos:
Input: N = 15, K = 3 Output: 2 15 is "1111", hence the third bit is at index 2 from right. Input: N = 19, K = 2 Output: 1 19 is "10011", hence the second set bit is at index 1 from right.
Enfoque: Inicialice un contador 0 y auméntelo si el último bit está establecido en el número. Para acceder al siguiente bit, desplaza el número a la derecha en 1. Cuando el valor del contador es igual a K, devolvemos el índice del número que se incrementaba en cada desplazamiento a la derecha.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns the Kth set bit
int FindIndexKthBit(int n, int k)
{
int cnt = 0;
int ind = 0;
// Traverse in the binary
while (n) {
// Check if the last
// bit is set or not
if (n & 1)
cnt++;
// Check if count is equal to k
// then return the index
if (cnt == k)
return ind;
// Increase the index
// as we move right
ind++;
// Right shift the number by 1
n = n >> 1;
}
return -1;
}
// Driver Code
int main()
{
int n = 15, k = 3;
int ans = FindIndexKthBit(n, k);
if (ans != -1)
cout << ans;
else
cout << "No k-th set bit";
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function that returns the Kth set bit
static int FindIndexKthBit(int n, int k)
{
int cnt = 0;
int ind = 0;
// Traverse in the binary
while (n > 0)
{
// Check if the last
// bit is set or not
if ((n & 1 ) != 0)
cnt++;
// Check if count is equal to k
// then return the index
if (cnt == k)
return ind;
// Increase the index
// as we move right
ind++;
// Right shift the number by 1
n = n >> 1;
}
return -1;
}
// Driver Code
public static void main(String args[])
{
int n = 15, k = 3;
int ans = FindIndexKthBit(n, k);
if (ans != -1)
System.out.println(ans);
else
System.out.println("No k-th set bit");
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 implementation of the approach
# Function that returns the Kth set bit
def FindIndexKthBit(n, k):
cnt, ind = 0, 0
# Traverse in the binary
while n > 0:
# Check if the last
# bit is set or not
if n & 1:
cnt += 1
# Check if count is equal to k
# then return the index
if cnt == k:
return ind
# Increase the index
# as we move right
ind += 1
# Right shift the number by 1
n = n >> 1
return -1
# Driver Code
if __name__ == "__main__":
n, k = 15, 3
ans = FindIndexKthBit(n, k)
if ans != -1:
print(ans)
else:
print("No k-th set bit")
# This code is contributed by
# Rituraj Jain
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function that returns the Kth set bit
static int FindIndexKthBit(int n, int k)
{
int cnt = 0;
int ind = 0;
// Traverse in the binary
while (n > 0)
{
// Check if the last
// bit is set or not
if ((n & 1 ) != 0)
cnt++;
// Check if count is equal to k
// then return the index
if (cnt == k)
return ind;
// Increase the index
// as we move right
ind++;
// Right shift the number by 1
n = n >> 1;
}
return -1;
}
// Driver Code
public static void Main()
{
int n = 15, k = 3;
int ans = FindIndexKthBit(n, k);
if (ans != -1)
Console.WriteLine(ans);
else
Console.WriteLine("No k-th set bit");
}
}
// This code is contributed by
// Code_Mech.
PHP
<?php
// PHP program to implement
// the above approach
// Function that returns the Kth set bit
function FindIndexKthBit($n, $k)
{
$cnt = 0;
$ind = 0;
// Traverse in the binary
while ($n)
{
// Check if the last
// bit is set or not
if ($n & 1)
$cnt++;
// Check if count is equal to k
// then return the index
if ($cnt == $k)
return $ind;
// Increase the index
// as we move right
$ind++;
// Right shift the number by 1
$n = $n >> 1;
}
return -1;
}
// Driver Code
$n = 15;
$k = 3;
$ans = FindIndexKthBit($n, $k);
if ($ans != -1)
echo $ans;
else
echo "No k-th set bit";
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program to implement
// the above approach
// Function that returns the Kth set bit
function FindIndexKthBit(n, k)
{
let cnt = 0;
let ind = 0;
// Traverse in the binary
while (n > 0) {
// Check if the last
// bit is set or not
if (n & 1 > 0)
cnt++;
// Check if count is equal to k
// then return the index
if (cnt == k)
return ind;
// Increase the index
// as we move right
ind++;
// Right shift the number by 1
n = n >> 1;
}
return -1;
}
let n = 15, k = 3;
let ans = FindIndexKthBit(n, k);
if (ans != -1)
document.write(ans);
else
document.write("No k-th set bit");
</script>
2
Complejidad de tiempo: O(logN), ya que estamos usando un bucle while para atravesar y en cada recorrido estamos desplazando N a la derecha en 1 lugar, lo que equivale a la división mínima de N entre 2. Por lo tanto, el tiempo efectivo será 1+1 /2+1/4+…..+1/2^N que es equivalente a logN.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.