Given a limit N, we need to find out the count of binary digit numbers which are smaller than N. Binary digit numbers are those numbers that contain only 0 and 1 as their digits, like 1, 10, 101, etc are binary digit numbers.
Examples:
Input : N = 200 Output : 7 Count of binary digit number smaller than N is 7, enumerated below, 1, 10, 11, 110, 101, 100, 111
One simple way to solve this problem is to loop from 1 to N and check each number whether it is a binary digit number or not. If it is a binary digit number, increase the count of such numbers, but this procedure will take O(N) time. We can do better, as we know that the count of such numbers will be much smaller than N. We can iterate over binary digit numbers only and check whether generated numbers are smaller than N or not.
In the code below, the BFS-like approach is implemented to iterate over only binary digit numbers. We start with 1 and each time we will push (t*10) and (t*10 + 1) into the queue where t is the popped element. If t is a binary digit number, then (t*10) and (t*10 + 1) will also number, so we will iterate over these numbers by only using the queue. We will stop pushing elements in the queue when popped number crosses the N.
C++
// C++ program to count all binary digit// numbers smaller than N#include <bits/stdc++.h>using namespace std;// method returns count of binary digit// numbers smaller than Nint countOfBinaryNumberLessThanN(int N){ // queue to store all intermediate binary // digit numbers queue<int> q; // binary digits start with 1 q.push(1); int cnt = 0; int t; // loop until we have element in queue while (!q.empty()) { t = q.front(); q.pop(); // push next binary digit numbers only if // current popped element is N if (t <= N) { cnt++; // uncomment below line to print actual // number in sorted order // cout << t << " "; q.push(t * 10); q.push(t * 10 + 1); } } return cnt;}// Driver code to test above methodsint main(){ int N = 200; cout << countOfBinaryNumberLessThanN(N); return 0;} |
Java
import java.util.LinkedList;import java.util.Queue;// java program to count all binary digit// numbers smaller than Npublic class GFG {// method returns count of binary digit// numbers smaller than N static int countOfBinaryNumberLessThanN(int N) { // queue to store all intermediate binary // digit numbers Queue<Integer> q = new LinkedList<>(); // binary digits start with 1 q.add(1); int cnt = 0; int t; // loop until we have element in queue while (q.size() > 0) { t = q.peek(); q.remove(); // push next binary digit numbers only if // current popped element is N if (t <= N) { cnt++; // uncomment below line to print actual // number in sorted order // cout << t << " "; q.add(t * 10); q.add(t * 10 + 1); } } return cnt; }// Driver code to test above methods static public void main(String[] args) { int N = 200; System.out.println(countOfBinaryNumberLessThanN(N)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to count all binary digit# numbers smaller than Nfrom collections import deque# method returns count of binary digit# numbers smaller than Ndef countOfBinaryNumberLessThanN(N): # queue to store all intermediate binary # digit numbers q = deque() # binary digits start with 1 q.append(1) cnt = 0 # loop until we have element in queue while (q): t = q.popleft() # push next binary digit numbers only if # current popped element is N if (t <= N): cnt = cnt + 1 # uncomment below line to print actual # number in sorted order q.append(t * 10) q.append(t * 10 + 1) return cnt# Driver code to test above methodsif __name__=='__main__': N = 200 print(countOfBinaryNumberLessThanN(N))# This code is contributed by# Sanjit_Prasad |
C#
// C# program to count all binary digit // numbers smaller than N using System;using System.Collections.Generic;class GFG { // method returns count of binary digit // numbers smaller than N static int countOfBinaryNumberLessThanN(int N) { // queue to store all intermediate binary // digit numbers Queue<int> q = new Queue<int>(); // binary digits start with 1 q.Enqueue(1); int cnt = 0; int t; // loop until we have element in queue while (q.Count > 0) { t = q.Peek(); q.Dequeue(); // push next binary digit numbers only if // current popped element is N if (t <= N) { cnt++; // uncomment below line to print actual // number in sorted order q.Enqueue(t * 10); q.Enqueue(t * 10 + 1); } } return cnt; } // Driver code static void Main() { int N = 200; Console.WriteLine(countOfBinaryNumberLessThanN(N)); } } // This code is contributed by mits |
PHP
<?php// PHP program to count all binary digit// numbers smaller than N// method returns count of binary digit// numbers smaller than Nfunction countOfBinaryNumberLessThanN($N){ // queue to store all intermediate // binary digit numbers $q = array(); // binary digits start with 1 array_push($q, 1); $cnt = 0; $t = 0; // loop until we have element in queue while (!empty($q)) { $t = array_pop($q); // push next binary digit numbers only // if current popped element is N if ($t <= $N) { $cnt++; // uncomment below line to print // actual number in sorted order // cout << t << " "; array_push($q, $t * 10); array_push($q, ($t * 10 + 1)); } } return $cnt;}// Driver Code$N = 200;echo countOfBinaryNumberLessThanN($N);// This code is contributed by mits?> |
Javascript
<script> // JavaScript program to count all binary digit // numbers smaller than N // method returns count of binary digit // numbers smaller than N function countOfBinaryNumberLessThanN(N) { // queue to store all intermediate binary // digit numbers var q = []; // binary digits start with 1 q.push(1); var cnt = 0; var t; // loop until we have element in queue while (q.length > 0) { t = q.pop(); // push next binary digit numbers only if // current popped element is N if (t <= N) { cnt++; // uncomment below line to print actual // number in sorted order q.push(t * 10); q.push(t * 10 + 1); } } return cnt; } // Driver code var N = 200; document.write(countOfBinaryNumberLessThanN(N) + "<br>");</script> |
Output:
7
Time complexity: O(log10N)
Auxiliary space: O(log10N) for queue q
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
