Count of Binary Digit numbers smaller than N

https://www.geeksforgeeks.org/count-binary-digit-numbers-smaller-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

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.

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

    }




https://www.geeksforgeeks.org/nth-number-made-up-of-odd-digits-only/

Given an integer N, the task is to find the Nth number made up of odd digits (1, 3, 5, 7, 9) only.
First few numbers made up of odd digits are 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, …

Approach 2 (Queue Based): The idea is to generate all numbers (smaller than n) containing odd digits only. How to generate all numbers smaller than n with odd digits? We use queue for this. Initially we push ‘1’, ‘3’, ‘5’, ‘7’ and ‘9’ to the queue. Then we run a loop while count of processed elements is smaller than n. We pop an item one by one and for every popped item x, we generate next numbers x*10 + 1, x*10 + 3, x*10 + 5, x*10 + 7 and x*10 + 9. We enqueue these new numbers. Time complexity of this approach is O(n)