# Count of Binary Digit numbers smaller than N

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 which contains only 0 and 1 as their digits as 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

One simple way to solve this problem is to loop from 1 till 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 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 below code, 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 binary digit number, so we will iterate over these numbers only using 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 ` `using` `namespace` `std; ` ` `  `//  method returns count of binary digit ` `//  numbers smaller than N ` `int` `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 untill 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 methods ` `int` `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 N ` `public` `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 q = ``new` `LinkedList<>(); ` ` `  `        ``//  binary digits start with 1 ` `        ``q.add(``1``); ` `        ``int` `cnt = ``0``; ` `        ``int` `t; ` ` `  `        ``//  loop untill 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 N ` `from` `collections ``import` `deque ` ` `  `# method returns count of binary digit ` `# numbers smaller than N ` `def` `countOfBinaryNumberLessThanN(N): ` `    ``# queue to store all intermediate binary ` `    ``# digit numbers ` `    ``q ``=` `deque() ` ` `  `    ``# binary digits start with 1 ` `    ``q.append(``1``) ` `    ``cnt ``=` `0` ` `  `    ``# loop untill 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 methods ` `if` `__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 untill 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

 ` `

Output:

```7
```