Given a number N, the task is to find a number in the range from 1 to N such that its digit sum is maximum. If there are several such numbers, print the biggest of them.
Example 1:
Input:
N = 48
Output: 48
Explanation:
There are two numbers with maximum digit sum. 
The numbers are 48 and 39 Since 48 > 39, 
it is our answer.
 
Example 2:
Input:
N = 90
Output: 89
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findMax() which takes the integer N as input parameters and returns the biggest number having the maximum sum.
Expected Time Complexity: O(M) where M is the number of digits in n.
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{18}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def findMax (self, N):

        pass

        # code here



Solutions:
class Solution:

	def findMax(self, N):
		pass

		def sum(N):
			s = N
			sum = 0
			while s != 0:
				sum += s % 10
				s = s // 10
			return sum
		ans = N
		b = 1
		x = N
		while x > 0:
			conversion9 = (x - 1) * b + (b - 1)
			if sum(ans) > sum(conversion9) or (sum(ans) == sum(conversion9) and ans > conversion9):
				ans = ans
			else:
				ans = conversion9
			x = x // 10
			b *= 10
		return ans


class Solution:

	def findMax(self, N):
		pass
		if N < 10:
			return N

		def sum_no(temp):
			sum1 = 0
			while temp > 0:
				sum1 = sum1 + temp % 10
				temp = temp // 10
			return sum1
		x = N
		sol = x
		a = 1
		while x > 0:
			convert = (x - 1) * a + a - 1
			if (sum_no(sol) > sum_no(convert) or sum_no(sol) == sum_no(convert)) and sol > convert:
				sol = sol
			else:
				sol = convert
			x = x // 10
			a *= 10
		return sol


class Solution:

	def findMax(self, N):
		X = N
		s = 0
		d = 0
		e = 0
		while N != 0:
			e = N % 10
			s += e
			d += 1
			N = N // 10
		if e - 1 + (d - 1) * 9 <= s:
			return X
		if int(str(e) + '8' + (d - 2) * '9') <= X:
			return str(e) + '8' + (d - 2) * '9'
		return (str(e - 1) + str(9) * (d - 1)).lstrip('0')


class Solution:

	def findMax(self, N):

		def dsum(n):
			s = 0
			while n > 0:
				s += n % 10
				n //= 10
			return s
		b = 1
		ans = N
		while N != 0:
			cur = (N - 1) * b + (b - 1)
			if dsum(cur) > dsum(ans) or (dsum(cur) == dsum(ans) and cur > ans):
				ans = cur
			N //= 10
			b = b * 10
		return ans


def sumOfDigits(a):
	sm = 0
	while a != 0:
		sm = sm + a % 10
		a = a // 10
	return sm

class Solution:

	def findMax(self, x):
		pass
		b = 1
		ans = x
		while x != 0:
			cur = (x - 1) * b + (b - 1)
			if sumOfDigits(cur) > sumOfDigits(ans) or (sumOfDigits(cur) == sumOfDigits(ans) and cur > ans):
				ans = cur
			x = x // 10
			b = b * 10
		return ans