Last Updated: 14 Apr, 2021
Count Number Of Ones
Hard
Asked in companies
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’.
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.
Approaches
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.
We will use digit dp to count the number of ones from 0 to N.To know more about digit dp refer to this https://codeforces.com/blog/entry/53960
We will create dp with state dp[Index][Total][Check] such that:
- Index:- It will tell about the index value from the left in the given integer.
- Total:- It will keep the count of a total number of ones from left to index.
- Check:- It will tell if the current digit range is restricted or not. If it is not restricted it will span from 0 to 9.Else it will span from 0 to digit[index].
The state dp[index][total][check] will tell about the total number of ones possible from the current index to the rightmost index according to the check condition.
Algorithm :
- Create an auxiliary 3D array dp[log(N)][log(N)][2] with initial value equal -1.
- Convert the integer N into a digits array.
- Create a function calculate(Index=0,Total=0,Check=1) for memoization.
- The base case will be if Index==digits.length() then return total.
- Add another if dp[Index][Total][Check] not equal to -1 then return dp[Index][Total][Check] .
- If the check will be 1 then the digit range at Index will be from 0 to digit[Index] else it will be from 0 to 9.
- The recursive call will be:-
- The current state dp[Index][Total][Check]=tot.
- Return the tot.