Find the number of integers from 1 to n which contains digits 0’s and 1’s only

0 0 3 minutes read

Given a number N. The task is to find the number of integers from 1 to n which contains digits 0’s and 1’s only.

Examples:

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.

Approach: An efficient approach is to build integers which contain 1’s and 0’s only using a recursive function starting from the number 1. For each number check whether it is less than n or not.

Below is the implementation of the above approach:

C++

// 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

// 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

# 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#

// 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
// 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.
?>

Javascript

<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>

Output:

Time Complexity: O((log₁₀n))

Auxiliary Space: O((log₁₀n))

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!