Dados dos números enteros N y K , la tarea es encontrar el conteo de bits establecidos en el K -ésimo número en la secuencia Par-Impar hecha del número del rango [1, N] . La secuencia Par-Impar contiene primero todos los números impares del 1 al N y luego todos los números pares del 1 al N.
Ejemplos:
Entrada: N = 8, K = 4
Salida: 3
La secuencia es 1, 3, 5, 7, 2, 4, 6 y 8. El
cuarto elemento es 7 y el número
de bits establecidos en él es 3.
Entrada: N = 18, K = 12
Salida: 2
Enfoque: En este artículo se ha discutido un enfoque para encontrar el elemento K-ésimo de la secuencia requerida . Entonces, encuentre el número requerido y luego use __builtin_popcount() para encontrar el conteo de bits establecidos en él.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the kth element
// of the Odd-Even sequence
// of length n
int findK(int n, int k)
{
int pos;
// Finding the index from where the
// even numbers will be stored
if (n % 2 == 0) {
pos = n / 2;
}
else {
pos = (n / 2) + 1;
}
// Return the kth element
if (k <= pos) {
return (k * 2 - 1);
}
else
return ((k - pos) * 2);
}
// Function to return the count of
// set bits in the kth number of the
// odd even sequence of length n
int countSetBits(int n, int k)
{
// Required kth number
int kth = findK(n, k);
// Return the count of set bits
return __builtin_popcount(kth);
}
// Driver code
int main()
{
int n = 18, k = 12;
cout << countSetBits(n, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the kth element
// of the Odd-Even sequence
// of length n
static int findK(int n, int k)
{
int pos;
// Finding the index from where the
// even numbers will be stored
if (n % 2 == 0)
{
pos = n / 2;
}
else
{
pos = (n / 2) + 1;
}
// Return the kth element
if (k <= pos)
{
return (k * 2 - 1);
}
else
return ((k - pos) * 2);
}
// Function to return the count of
// set bits in the kth number of the
// odd even sequence of length n
static int countSetBits(int n, int k)
{
// Required kth number
int kth = findK(n, k);
int count = 0;
while (kth > 0)
{
count += kth & 1;
kth >>= 1;
}
// Return the count of set bits
return count;
}
// Driver code
public static void main (String[] args)
{
int n = 18, k = 12;
System.out.println(countSetBits(n, k));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach
# Function to return the kth element
# of the Odd-Even sequence
# of length n
def findK(n, k) :
# Finding the index from where the
# even numbers will be stored
if (n % 2 == 0) :
pos = n // 2;
else :
pos = (n // 2) + 1;
# Return the kth element
if (k <= pos) :
return (k * 2 - 1);
else :
return ((k - pos) * 2);
# Function to return the count of
# set bits in the kth number of the
# odd even sequence of length n
def countSetBits( n, k) :
# Required kth number
kth = findK(n, k);
# Return the count of set bits
return bin(kth).count('1');
# Driver code
if __name__ == "__main__" :
n = 18; k = 12;
print(countSetBits(n, k));
# This code is contributed by kanugargng
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the kth element
// of the Odd-Even sequence
// of length n
static int findK(int n, int k)
{
int pos;
// Finding the index from where the
// even numbers will be stored
if (n % 2 == 0)
{
pos = n / 2;
}
else
{
pos = (n / 2) + 1;
}
// Return the kth element
if (k <= pos)
{
return (k * 2 - 1);
}
else
return ((k - pos) * 2);
}
// Function to return the count of
// set bits in the kth number of the
// odd even sequence of length n
static int countSetBits(int n, int k)
{
// Required kth number
int kth = findK(n, k);
int count = 0;
while (kth > 0)
{
count += kth & 1;
kth >>= 1;
}
// Return the count of set bits
return count;
}
// Driver code
public static void Main (String[] args)
{
int n = 18, k = 12;
Console.WriteLine(countSetBits(n, k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function to return the kth element
// of the Odd-Even sequence
// of length n
function findK(n, k)
{
let pos;
// Finding the index from where the
// even numbers will be stored
if (n % 2 == 0)
{
pos = parseInt(n / 2, 10);
}
else
{
pos = parseInt(n / 2, 10) + 1;
}
// Return the kth element
if (k <= pos)
{
return (k * 2 - 1);
}
else
{
return ((k - pos) * 2);
}
}
// Function to return the count of
// set bits in the kth number of the
// odd even sequence of length n
function countSetBits(n, k)
{
// Required kth number
let kth = findK(n, k);
let count = 0;
while (kth > 0)
{
count += kth & 1;
kth >>= 1;
}
// Return the count of set bits
return count;
}
let n = 18, k = 12;
document.write(countSetBits(n, k));
</script>
Producción:
2
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por isa_aanchal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA