Given N coins, the sequence of numbers consists of {1, 2, 3, 4, ……..}. The cost for choosing a number in a sequence is the number of digits it contains. (For example cost of choosing 2 is 1 and for 999 is 3), the task is to print the Maximum number of elements a sequence can contain.
Any element from {1, 2, 3, 4, ……..}. can be used at most 1 time.
Examples:
Input: N = 11
Output: 10
Explanation: For N = 11 > selecting 1 with cost 1, 2 with cost 1, 3 with cost 1, 4 with cost 1, 5 with cost 1, 6 with cost 1, 7 with cost 1, 8 with cost 1, 9 with cost 1, 10 with cost 2.
totalCost = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 11.Input: N = 189
Output: 99
Naive approach: The basic way to solve the problem is as follows:
Iterate i from 1 to infinity and calculate the cost for current i if the cost for i is more than the number of coins which is N then i – 1 will be the answer.
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
This Problem can be solved using Binary Search. A number of digits with given cost is a monotonic function of type T T T T T F F F F. Last time the function was true will generate an answer for the Maximum length of the sequence.
Follow the steps below to solve the problem:
 If the cost required for digits from 1 to mid is less than equal to N update low with mid.
 Else high with mid – 1 by ignoring the right part of the search space.
 For printing answers after binary search check whether the number of digits from 1 to high is less than or equal to N if this is true print high
 Then check whether the number of digits from 1 to low is less than or equal to N if this is true print low.
 Finally, if nothing gets printed from above print 0 since the length of the sequence will be 0.
Below is the implementation of the above approach:
C++

Time Complexity: O(logN^{2}) (first logN is for logN operations of binary search, the second logN is for finding the number of digits from 1 to N)
Auxiliary Space: O(1)
Related Articles: