Given N cash, the sequence of numbers consists of {1, 2, 3, 4, ……..}. The fee for selecting a quantity in a sequence is the variety of digits it incorporates. (For instance value of selecting 2 is 1 and for 999 is 3), the duty is to print the Most variety of parts a sequence can comprise.
Any component from {1, 2, 3, 4, ……..}. can be utilized at most 1 time.
Examples:
Enter: N = 11
Output: 10
Rationalization: For N = 11 -> deciding on 1 with value 1, 2 with value 1, 3 with value 1, 4 with value 1, 5 with value 1, 6 with value 1, 7 with value 1, 8 with value 1, 9 with value 1, 10 with value 2.
totalCost = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 11.Enter: N = 189
Output: 99
Naive strategy: The essential option to clear up the issue is as follows:
Iterate i from 1 to infinity and calculate the associated fee for present i if the associated fee for i is greater than the variety of cash which is N then i – 1 would be the reply.
Time Complexity: O(N * logN)
Auxiliary House: O(1)
Environment friendly Strategy: The above strategy may be optimized primarily based on the next thought:
This Drawback may be solved utilizing Binary Search. Numerous digits with given value is a monotonic operate of kind T T T T T F F F F. Final time the operate was true will generate a solution for the Most size of the sequence.
Comply with the steps under to resolve the issue:
- If the associated fee required for digits from 1 to mid is lower than equal to N replace low with mid.
- Else excessive with mid – 1 by ignoring the best a part of the search house.
- For printing solutions after binary search test whether or not the variety of digits from 1 to excessive is lower than or equal to N if that is true print excessive
- Then test whether or not the variety of digits from 1 to low is lower than or equal to N if that is true print low.
- Lastly, if nothing will get printed from above print 0 for the reason that size of the sequence might be 0.
Beneath is the implementation of the above strategy:
C++
|
|
Time Complexity: O(logN2) (first logN is for logN operations of binary search, the second logN is for locating the variety of digits from 1 to N)
Auxiliary House: O(1)
Associated Articles:
