Dado un número X, la tarea es encontrar el número mínimo N tal que el conjunto total de bits de todos los números del 1 al n sea al menos X.
Ejemplos:
Input: x = 5 Output: 4 Set bits in 1-> 1 Set bits in 2-> 1 Set bits in 3-> 2 Set bits in 4-> 1 Hence first four numbers add upto 5 Input: x = 20 Output: 11
Enfoque: use la búsqueda binaria para obtener el número máximo mínimo cuya suma de bits hasta N sea al menos X. Al principio, el valor bajo es 0 y el valor alto se inicializa de acuerdo con la restricción. Verifique si el conteo de bits establecidos es al menos X, cada vez que lo sea, cambie alto a mid-1, de lo contrario, cámbielo a mid+1. Cada vez que hacemos high = mid-1, almacenamos el mínimo de respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define INF 99999
#define size 10
// Function to count sum of set bits
// of all numbers till N
int getSetBitsFromOneToN(int N)
{
int two = 2, ans = 0;
int n = N;
while (n) {
ans += (N / two) * (two >> 1);
if ((N & (two - 1)) > (two >> 1) - 1)
ans += (N & (two - 1)) - (two >> 1) + 1;
two <<= 1;
n >>= 1;
}
return ans;
}
// Function to find the minimum number
int findMinimum(int x)
{
int low = 0, high = 100000;
int ans = high;
// Binary search for the lowest number
while (low <= high) {
// Find mid number
int mid = (low + high) >> 1;
// Check if it is atleast x
if (getSetBitsFromOneToN(mid) >= x) {
ans = min(ans, mid);
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code
int main()
{
int x = 20;
cout << findMinimum(x);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class solution
{
static int INF = 99999;
static int size = 10;
// Function to count sum of set bits
// of all numbers till N
static int getSetBitsFromOneToN(int N)
{
int two = 2, ans = 0;
int n = N;
while (n!=0) {
ans += (N / two) * (two >> 1);
if ((N & (two - 1)) > (two >> 1) - 1)
ans += (N & (two - 1)) - (two >> 1) + 1;
two <<= 1;
n >>= 1;
}
return ans;
}
// Function to find the minimum number
static int findMinimum(int x)
{
int low = 0, high = 100000;
int ans = high;
// Binary search for the lowest number
while (low <= high) {
// Find mid number
int mid = (low + high) >> 1;
// Check if it is atleast x
if (getSetBitsFromOneToN(mid) >= x) {
ans = Math.min(ans, mid);
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int x = 20;
System.out.println(findMinimum(x));
}
}
//This code is contributed by
// Shashank_Sharma
Python3
# Python3 implementation of the # above approach INF = 99999 size = 10 # Function to count sum of set bits # of all numbers till N def getSetBitsFromOneToN(N): two, ans = 2, 0 n = N while (n > 0): ans += (N // two) * (two >> 1) if ((N & (two - 1)) > (two >> 1) - 1): ans += (N & (two - 1)) - (two >> 1) + 1 two <<= 1 n >>= 1 return ans # Function to find the minimum number def findMinimum(x): low = 0 high = 100000 ans = high # Binary search for the lowest number while (low <= high): # Find mid number mid = (low + high) >> 1 # Check if it is atleast x if (getSetBitsFromOneToN(mid) >= x): ans = min(ans, mid) high = mid - 1 else: low = mid + 1 return ans # Driver Code x = 20 print(findMinimum(x)) # This code is contributed by # Mohit kumar 29
C#
// C# implementation of the above approach
using System ;
class solution
{
static int INF = 99999;
static int size = 10;
// Function to count sum of set bits
// of all numbers till N
static int getSetBitsFromOneToN(int N)
{
int two = 2, ans = 0;
int n = N;
while (n!=0) {
ans += (N / two) * (two >> 1);
if ((N & (two - 1)) > (two >> 1) - 1)
ans += (N & (two - 1)) - (two >> 1) + 1;
two <<= 1;
n >>= 1;
}
return ans;
}
// Function to find the minimum number
static int findMinimum(int x)
{
int low = 0, high = 100000;
int ans = high;
// Binary search for the lowest number
while (low <= high) {
// Find mid number
int mid = (low + high) >> 1;
// Check if it is atleast x
if (getSetBitsFromOneToN(mid) >= x) {
ans = Math.Min(ans, mid);
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code
public static void Main()
{
int x = 20;
Console.WriteLine(findMinimum(x));
}
// This code is contributed by Ryuga
}
PHP
<?php
// PHP implementation of the above approach
// Function to count sum of set bits
// of all numbers till N
function getSetBitsFromOneToN($N)
{
$two = 2;
$ans = 0;
$n = $N;
while ($n)
{
$ans += (int)($N / $two) * ($two >> 1);
if (($N & ($two - 1)) > ($two >> 1) - 1)
$ans += ($N & ($two - 1)) -
($two >> 1) + 1;
$two <<= 1;
$n >>= 1;
}
return $ans;
}
// Function to find the minimum number
function findMinimum($x)
{
$low = 0;
$high = 100000;
$ans = $high;
// Binary search for the lowest number
while ($low <= $high)
{
// Find mid number
$mid = ($low + $high) >> 1;
// Check if it is atleast x
if (getSetBitsFromOneToN($mid) >= $x)
{
$ans = min($ans, $mid);
$high = $mid - 1;
}
else
$low = $mid + 1;
}
return $ans;
}
// Driver Code
$x = 20;
echo findMinimum($x);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// Javascript implementation of the above approach
const INF = 99999;
const size = 10;
// Function to count sum of set bits
// of all numbers till N
function getSetBitsFromOneToN(N)
{
let two = 2, ans = 0;
let n = N;
while (n)
{
ans += parseInt(N / two) * (two >> 1);
if ((N & (two - 1)) > (two >> 1) - 1)
ans += (N & (two - 1)) - (two >> 1) + 1;
two <<= 1;
n >>= 1;
}
return ans;
}
// Function to find the minimum number
function findMinimum(x)
{
let low = 0, high = 100000;
let ans = high;
// Binary search for the lowest number
while (low <= high)
{
// Find mid number
let mid = (low + high) >> 1;
// Check if it is atleast x
if (getSetBitsFromOneToN(mid) >= x)
{
ans = Math.min(ans, mid);
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
// Driver Code
let x = 20;
document.write(findMinimum(x));
// This code is contributed by subhammahato348
</script>
Producción:
11
Complejidad de tiempo: O (log N * log N), getSetBitsFromOneToN tomará logN tiempo ya que estamos usando el desplazamiento bit a bit a la derecha en cada recorrido, que es equivalente a la división de piso con 2 en cada recorrido, por lo que el costo será 1+1/2 +1/4+….+1/2 N que equivale a logN. Estamos usando la búsqueda binaria y cada vez llamamos a la función getSetBitsFromOneToN . La búsqueda binaria también toma el tiempo logN a medida que disminuimos cada vez por división mínima de 2. Por lo tanto, el costo efectivo del programa será O(logN*logN).
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.