Geek has a unique keyboard containing only the numpad keys. ie - 1,2,3,4,5,6,7,8,9,0. But the keyboard is damaged and can only process M keys. Geek is supposed to use the keyboard to type as many natural numbers as possible starting from 1. What will be the greatest natural number he will type?
Example 1:
Input:
M = 5
Output: 5
Explaination:
Geek can only press 5 keys. He will type
1,2,3,4,5. The greatest number is 5.
Example 2:
Input:
M = 15
Output: 12
Explaination:
1 key each from 1 to 9.
2 keys each from 10 to 12.
Total keys pressed = 15.
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxNatural() which takes M as input parameter and returns the maximum natural number possible to get after pressing M keys.
Expected Time Complexity: O(logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ M ≤ 38890

见题面

见题面