Finding Binary In Decimal

Easy
0/40
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in company
Infosys

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample input 1 :

2
10
21

Sample output 1 :

2
3

Explanation for sample input 1 :

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) 

Sample input 2 :

3
250
1505
3010

Sample output 2 :

7
15
15
Approaches (2)
Brute force 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.
Time Complexity

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.


 

Space Complexity

O(1)

 

No extra space has been used

 

Code Solution
(100% EXP penalty)
Finding Binary In Decimal
Full screen
Console