Dado un número entero N , la tarea es encontrar el N número natural con exactamente dos bits establecidos.
Ejemplos:
Entrada: N = 4
Salida: 9
Explicación: Los números con exactamente dos bits establecidos son 3, 5, 6, 9, 10, 12, ….
El cuarto término de esta serie es 9.Entrada: N = 15
Salida: 48
Explicación: Los números con exactamente dos bits establecidos son 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48…. El término
15 de esta serie es 48.
Enfoque ingenuo: consulte la publicación anterior de este artículo para obtener la solución más simple posible para este problema.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea de utilizar la búsqueda binaria para encontrar el número N. Siga los pasos a continuación para resolver el problema:
- Cualquier número en la serie dada está en la forma (2 a + 2 b ) donde a > b .
- El N -ésimo término de una serie se puede identificar identificando los valores a y b .
- Encuentre el valor de a tal que (a * (a + 1)) / 2 ≥ N y manteniendo la restricción de que a debe ser mínimo
- Por lo tanto, encuentre el valor de a para las restricciones en los pasos anteriores utilizando la búsqueda binaria.
- Después de los pasos anteriores, encuentre el valor de b usando a y N e imprima el resultado como (2 a + 2 b ) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the Nth number
// with exactly two bits set
void findNthNum(long long int N)
{
// Initialize variables
long long int a, b, left;
long long int right, mid;
long long int t, last_num = 0;
// Initialize the range in which
// the value of 'a' is present
left = 1, right = N;
// Perform Binary Search
while (left <= right) {
// Find the mid value
mid = left + (right - left) / 2;
t = (mid * (mid + 1)) / 2;
// Update the range using the
// mid value t
if (t < N) {
left = mid + 1;
}
else if (t == N) {
a = mid;
break;
}
else {
a = mid;
right = mid - 1;
}
}
// Find b value using a and N
t = a - 1;
b = N - (t * (t + 1)) / 2 - 1;
// Print the value 2^a + 2^b
cout << (1 << a) + (1 << b);
}
// Driver Code
int main()
{
long long int N = 15;
// Function Call
findNthNum(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the Nth number
// with exactly two bits set
static void findNthNum(int N)
{
// Initialize variables
int a = 0, b, left;
int right, mid;
int t, last_num = 0;
// Initialize the range in which
// the value of 'a' is present
left = 1;
right = N;
// Perform Binary Search
while (left <= right) {
// Find the mid value
mid = left + (right - left) / 2;
t = (mid * (mid + 1)) / 2;
// Update the range using the
// mid value t
if (t < N) {
left = mid + 1;
}
else if (t == N) {
a = mid;
break;
}
else {
a = mid;
right = mid - 1;
}
}
// Find b value using a and N
t = a - 1;
b = N - (t * (t + 1)) / 2 - 1;
// Print the value 2^a + 2^b
System.out.print((1 << a) + (1 << b));
}
// Driver Code
public static void main(String[] args)
{
int N = 15;
// Function Call
findNthNum(N);
}
}
// This code contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to find the Nth number # with exactly two bits set def findNthNum(N): # Initialize variables last_num = 0 # Initialize the range in which # the value of 'a' is present left = 1 right = N # Perform Binary Search while (left <= right): # Find the mid value mid = left + (right - left) // 2 t = (mid * (mid + 1)) // 2 # Update the range using the # mid value t if (t < N): left = mid + 1 elif (t == N): a = mid break else: a = mid right = mid - 1 # Find b value using a and N t = a - 1 b = N - (t * (t + 1)) // 2 - 1 # Print the value 2^a + 2^b print((1 << a) + (1 << b)) # Driver Code if __name__ == "__main__": N = 15 # Function Call findNthNum(N) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the Nth number
// with exactly two bits set
static void findNthNum(int N)
{
// Initialize variables
int a = 0, b, left;
int right, mid;
int t;
//int last_num = 0;
// Initialize the range in which
// the value of 'a' is present
left = 1; right = N;
// Perform Binary Search
while (left <= right)
{
// Find the mid value
mid = left + (right - left) / 2;
t = (mid * (mid + 1)) / 2;
// Update the range using the
// mid value t
if (t < N)
{
left = mid + 1;
}
else if (t == N)
{
a = mid;
break;
}
else
{
a = mid;
right = mid - 1;
}
}
// Find b value using a and N
t = a - 1;
b = N - (t * (t + 1)) / 2 - 1;
// Print the value 2^a + 2^b
Console.Write((1 << a) + (1 << b));
}
// Driver Code
public static void Main()
{
int N = 15;
// Function Call
findNthNum(N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the Nth number
// with exactly two bits set
function findNthNum(N)
{
// Initialize variables
let a = 0, b, left;
let right, mid;
let t, last_num = 0;
// Initialize the range in which
// the value of 'a' is present
left = 1;
right = N;
// Perform Binary Search
while (left <= right) {
// Find the mid value
mid = left + (right - left) / 2;
t = (mid * (mid + 1)) / 2;
// Update the range using the
// mid value t
if (t < N) {
left = mid + 1;
}
else if (t == N) {
a = mid;
break;
}
else {
a = mid;
right = mid - 1;
}
}
// Find b value using a and N
t = a - 1;
b = N - (t * (t + 1)) / 2 - 1;
// Print the value 2^a + 2^b
document.write((1 << a) + (1 << b));
}
// Driver Code
let N = 15;
// Function Call
findNthNum(N);
</script>
Producción:
48
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saideepgummadavelly y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA