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 onlyint 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 codeint 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 onlyclass GFG{ // Function to find the number of integers// from 1 to n which contains 0's and 1's onlystatic 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 codepublic 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 onlyfunction 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 onlyfunction 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 codelet n = 120;document.write(countNumbers(1, n));// This code is contributed by Manoj.</script> |
Output:
7
Time Complexity: O((log10n))
Auxiliary Space: O((log10n))
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
