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

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def maxNatural(self, M):

        # code here

Solutions:
class Solution:

	def maxNatural(self, M):
		if M <= 9:
			return M
		M -= 9
		if M <= 180:
			M = M // 2
			return 9 + M
		M -= 180
		if M <= 2700:
			M = M // 3
			return 99 + M
		M -= 2700
		if M <= 36000:
			M = M // 4
			return 999 + M
		M -= 36000
		if M <= 38890:
			M = M // 5
			return 9999 + M
		return 0


class Solution:

	def maxNatural(self, M):
		(l, c) = (0, 0)
		d = 9 * pow(10, l)
		l += 1
		while d <= M:
			c += d // l
			M = M - d
			d = 9 * pow(10, l) * (l + 1)
			l += 1
		return c + M // l


class Solution:

	def maxNatural(self, M):
		(lent, count) = (0, 0)
		digits = 9 * pow(10, lent)
		lent += 1
		while digits <= M:
			count += digits // lent
			M = M - digits
			digits = 9 * pow(10, lent) * (lent + 1)
			lent += 1
		return count + M // lent