Encuentre el número de enteros del 1 al n que contienen dígitos 0 y 1 solamente

Dado un número N. La tarea es encontrar el número de enteros del 1 al n que contengan dígitos 0 y 1 solamente.

Ejemplos:  

Input : N = 15
Output : 3
Explanation : 1, 10, 11 are such integers.

Input : N = 120
Output : 7
Explanation : 1, 10, 11, 100, 101, 110, 111 
are such integers.

Enfoque : un enfoque eficiente es construir números enteros que contengan 1 y 0 solo usando una función recursiva que comience con el número 1. Para cada número, verifique si es menor que n o no.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find the number of integers
// from 1 to n which contains digits 0's and 1's only
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of integers
// from 1 to n which contains 0's and 1's only
int countNumbers(int x, int n)
{
    // If number is greater than n
    if (x > n)
        return 0;
 
    // otherwise add count this number and
    // call two functions
    return 1 + countNumbers(x * 10, n) + countNumbers(x * 10 + 1, n);
}
 
// Driver code
int main()
{
    int n = 120;
 
    cout << countNumbers(1, n);
 
    return 0;
}

// Java program to find the number of integers
// from 1 to n which contains digits 0's and 1's only
class GFG
{
     
// Function to find the number of integers
// from 1 to n which contains 0's and 1's only
static int countNumbers(int x, int n)
{
    // If number is greater than n
    if (x > n)
        return 0;
 
    // otherwise add count this number and
    // call two functions
    return 1 + countNumbers(x * 10, n) + countNumbers(x * 10 + 1, n);
}
 
// Driver code
public static void main (String[] args)
{
    int n = 120;
 
    System.out.println(countNumbers(1, n));
}
}
 
// This code is contributed by chandan_jnu

# Python3 program to find the number of
# integers from 1 to n which contains
# digits 0's and 1's only
 
# Function to find the number of integers
# from 1 to n which contains 0's and 1's only
def countNumbers(x, n):
     
    # If number is greater than n
    if x > n :
        return 0
 
    # otherwise add count this number and
    # call two functions
    return (1 + countNumbers(x * 10, n) +
                countNumbers(x * 10 + 1, n))
 
# Driver code
if __name__ == '__main__':
    n = 120;
 
    print(countNumbers(1, n));
     
# This code is contributed by Arnab Kundu

// C# program to find the number of integers
// from 1 to n which contains digits 0's and 1's only
using System;
 
class GFG
{
 
// Function to find the number of integers
// from 1 to n which contains 0's and 1's only
static int countNumbers(int x, int n)
{
    // If number is greater than n
    if (x > n)
        return 0;
 
    // otherwise add count this number and
    // call two functions
    return 1 + countNumbers(x * 10, n) +
               countNumbers(x * 10 + 1, n);
}
 
// Driver code
public static void Main()
{
    int n = 120;
 
    Console.WriteLine(countNumbers(1, n));
}
}
 
// This code is contributed by Ryuga

<?php
// PHP program to find the number of
// integers from 1 to n which contains
// digits 0's and 1's only
 
// Function to find the number of integers
// from 1 to n which contains 0's and 1's only
function countNumbers($x, $n)
{
    // If number is greater than n
    if ($x > $n)
        return 0;
 
    // otherwise add count this number and
    // call two functions
    return 1 + countNumbers($x * 10, $n) +
               countNumbers($x * 10 + 1, $n);
}
 
// Driver code
$n = 120;
 
echo(countNumbers(1, $n));
 
// This code is contributed
// by Code_Mech.
?>

<script>
 
// JavaScript program to find the
// number of integers from 1 to n
// which contains digits 0's and 1's only
 
// Function to find the number of
// integers from 1 to n which
// contains 0's and 1's only
function countNumbers(x, n)
{
     
    // If number is greater than n
    if (x > n)
        return 0;
 
    // Otherwise add count this number and
    // call two functions
    return 1 + countNumbers(x * 10, n) +
               countNumbers(x * 10 + 1, n);
}
 
// Driver code
 
let n = 120;
 
document.write(countNumbers(1, n));
 
// This code is contributed by Manoj.
 
</script>

7

Complejidad del tiempo: O((log ₁₀ n))

Espacio Auxiliar: O((log ₁₀ n))