Count Number Of Ones

Hard
0/120
Average time to solve is 45m
profile
Contributed by
6 upvotes
Asked in companies
AppleNovartis

Problem statement

Ninja has an integer ‘N’. Ninja is fond of digit ‘1’ so Ninja wants to know the number of 1s in each number from 0 to N.

Your task is to help the Ninja in finding out the number of ones from 0 to ‘N’.

Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first and only line of the test case consists of a single integer ‘N’.
Output Format 
Return the total number of one digit.
Constraints 
1 <= ‘T’ <= 11
1 <= ‘N’ <= 10^9

Time Limit: 1 sec
Note: 
 You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1
2
10
14
Sample Output 1
2
7
Explanation For Sample Input 1:
For the first test case:-

The number of 1’s in 1 is 1
The number of 1’s in 2 is 0
The number of 1’s in 3 is 0
The number of 1’s in 4 is 0
The number of 1’s in 5 is 0
The number of 1’s in 6 is 0
The number of 1’s in 7 is 0
The number of 1’s in 8 is 0
The number of 1’s in 9 is 0
The number of 1’s in 10 is 1

For the first test case hence answer is 2.

For the second test case:-

The number of 1’s in 1 is 1
The number of 1’s in 2 is 0
The number of 1’s in 3 is 0
The number of 1’s in 4 is 0
The number of 1’s in 5 is 0
The number of 1’s in 6 is 0
The number of 1’s in 7 is 0
The number of 1’s in 8 is 0
The number of 1’s in 9 is 0
The number of 1’s in 10 is 1
The number of 1’s in 11 is 2
The number of 1’s in 12 is 1
The number of 1’s in 13 is 1
The number of 1’s in 14 is 1

For the first test case hence answer is 7.
Sample Input 2
2
9
15
Sample Output 2
1
8
Hint

Count the number of ones from 0 to N.

Approaches (2)
Brute Force Approach

The main idea is to run a loop from 0 to N and count the number of ones for every integer from 0 to N.

 

Algorithm : 

 

  • Create a variable ‘ans’ with an initial value of 0.
  • Run a loop from 0 to N.
  • For every ‘i’ from 0 to N calculate the number of ones in ‘i’. Add it in the variable ‘ans’.
  • Return the ans.
Time Complexity

O(N * log10(N))  where ‘N’ is the given number.

 

For every integer from 0 to N, we are traversing its digits which takes O(log10(N)). Hence total time complexity is O(N * log10(N)).

Space Complexity

O(1) 

 

We are using constant space to solve this.

Code Solution
(100% EXP penalty)
Count Number Of Ones
Full screen
Console