Problem of the day
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.
1 <= T <= 10^4
1 <= N <= 10^9
Time Limit: 1sec
2
10
21
2
3
In first case, there are only 2 numbers between 1 to 10 that contain only 1s or 0s i.e (1,10)In second case, there are only 3 numbers containing only 0s and 1s i.e (1,10,11)
3
250
1505
3010
7
15
15
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:
O(N*log(N)) where ‘N’ is the given number.
We need to check for each number in the range of 1 to N and for checking we will check each digit which will take approximately O(log(N)) time.
O(1)
No extra space has been used