Last Updated: 11 Dec, 2020

Finding Binary In Decimal

Easy

Problem statement

Given an integer ‘N’, the task is to find the number of integers between 1 to N whose decimal number representation contains only 0s and 1s.

For example, 1011 , 11, 100 are all valid integers since they consist of 1s and 0s only, however 210, 3401 are not valid integers.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case has a single integer ‘N’ for which we need to find the integers containing only 0 and 1

Output Format :

For each test case, print the required count.

Constraints :

1 <= T <= 10^4
1 <= N <= 10^9

Time Limit: 1sec

Solve now

Approaches

01 Approach

For every integer between 1 to N , check whether it consists of 1s and 0s only.

If at any moment of time we found that there are other digit apart from 0s and 1s, then we will not count that integer in our answer.

Algorithm:

Run a for loop from 1 to N,
Pass every integer in a check_0_and_1() function
check0_and_1() function simply visits each digit

If any digit found apart from 0 and 1, return false
Else after checking each digit return true
If check0_and_1() function returns true, increment answer variable,
Else continue.

Solve now

02 Approach

Optimised way

In this approach, instead of visiting each and every number, we try to use the property of 1s and 0s. We have a range from 1 to N, and we know that 1 is a valid (one digit) number, and the next valid (2 digit) numbers are 10 , 11. So in order to reach 10, 11 from 1, we can simply multiply 1 by 10, and then

Add 0 to reach 10
Add 1 to reach 11

Using same thing,

/ \

10 11

/ \ / \

100 101 110 111

. . . .

If at any point we have reached a number larger than N, we can return from there. This way we are exploring all those numbers that consist of only 1s and 0s.

Algorithm

Since a tree-like structure is forming up, it's easier to use recursion. We only need to work at the root node, and recursion will handle children.

Create a helper function having our number N, and initial node i.e 1.

From 1, make two calls :

helper(N, node*10)
helper(N,node*10+1)

After that, add 1 in your ans because of the root node.

So it will look like,

Return helper(N,node*10) + helper(N,node*10+1) + 1

Stopping criteria (Base case)

Whenever we encounter a value greater than N, return 0 as it doesn’t fall in the given range.

Solve now