Los números de conteo tienen todos los 1 juntos en representación binaria

Dado un entero n , la tarea es contar el total de números de la suerte menores o iguales que n. Se dice que un número tiene suerte si tiene todos los números contagiosos de 1 en representación binaria desde el principio. Por ejemplo, 1, 3, 7, 15 son números de la suerte y 2, 5 y 9 no son números de la suerte.
Ejemplos: 
 

Input :n = 7 
Output :3
1, 3 and 7 are lucky numbers

Input :n = 17
Output :4

Enfoque: un enfoque es que primero descubrimos la representación binaria de cada número y luego verificamos el número contagioso de 1 para cada número, pero este enfoque lleva mucho tiempo y puede dar problemas si las restricciones son dos grandes. Se puede encontrar un enfoque eficiente al observar los números, podemos decir que cada i-ésimo número de la suerte se puede encontrar mediante la fórmula 2 ⁱ -1 , y al iterar un bucle hasta el número menor que igual a n podemos encontrar los números de la suerte totales.
A continuación se muestra la implementación del enfoque anterior. 
 

#include <bits/stdc++.h>
using namespace std;
 
int countLuckyNum(int n)
{
    int count = 0, i = 1;
 
    while (1) {
        if (n >= ((1 << i) - 1))
            count++;
        else
            break;
        i++;
    }
 
    return count;
}
 
// Driver code
int main()
{
    int n = 7;
    cout << countLuckyNum(n);
    return 0;
}

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class GFG {
 
    // Function to return the count of lucky number
    static int countLuckyNum(int n)
    {
 
        int count = 0, i = 1;
        while (true) {
            if (n >= ((1 << i) - 1))
                count++;
            else
                break;
            i++;
        }
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 7;
        System.out.println(countLuckyNum(n));
    }
}

# python3 code of above problem
 
# function to count the lucky number
 
def countLuckyNum(n):
     
    count, i = 0, 1
     
    while True:
        if n>= 2**i-1:
            count+= 1
        else:
            break
        i+= 1;
    return count    
 
# driver code
n = 7
 
print(countLuckyNum(n))

// C# implementation of the approach
using System;
 
public class GFG {
 
    // Function to return the count of lucky number
    static int countLuckyNum(int n)
    {
 
        int count = 0, i = 1;
        while (true) {
            if (n >= ((1 << i) - 1))
                count++;
            else
                break;
            i++;
        }
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 7;
        Console.WriteLine(countLuckyNum(n));
    }
}

<?php
// PHP implementation of the approach
   
// Function to count the lucky number
function countLuckyNum($n)  
{  
   
  $count = 0;
  $i = 1;
   
  while(1)
  {
      if ($n >= ((1 << $i) - 1))
        $count += 1;
      else
        break;
      $i += 1;
  }
  return $count;                    
}  
     
// Driver code  
$n = 7;
echo countLuckyNum($n) ;  
?>

<script>
 
    // Function to return the count of lucky number
    function countLuckyNum(n) {
 
        var count = 0, i = 1;
        while (true) {
            if (n >= ((1 << i) - 1))
                count++;
            else
                break;
            i++;
        }
        return count;
    }
 
    // Driver code
    var n = 7;
    document.write(countLuckyNum(n));
 
// This code is contributed by aashish1995
</script>

output:3

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)