Find the smallest number such that the sum of its digits is N and it is divisible by 10^{N}.
Example 1:
Input: N = 5
Outptut: 500000
Explanation: Sum of digits of 500000
is 5 and divisible by 10^{5}.
Example 2:
Input: N = 20
Output: 29900000000000000000000
Explanation: Sum of digits of 
29900000000000000000000 is 20 and
divisible by 10^{20}.
Your Task:
You don't need to read or print anything. Your task is to complete the function digitsNum() which takes the input parameter N and returns the smallest number such that sum of its digits is N and divisible by 10^{N}.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
 
Constraints:
1 <= N <= 10000

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

	def digitsNum(self, N):

		# Code here

Solutions:
class Solution:

	def digitsNum(self, N):
		sum = N
		l1 = ''
		while sum > 0:
			if sum > 9:
				l1 += '9'
			else:
				l1 += str(sum)
			sum -= 9
		l2 = l1[::-1]
		for i in range(N):
			l2 += '0'
		return l2


class Solution:

	def digitsNum(self, N):
		i = 9
		sno = '0' * N
		while N > 0:
			sno = N // i * str(i) + sno
			N %= i
			i -= 1
		return sno


class Solution:

	def digitsNum(self, N):
		sum = N
		m = ''
		while sum > 0:
			if sum > 9:
				m += '9'
			else:
				m += str(sum)
			sum -= 9
		m1 = m[::-1]
		for i in range(N):
			m1 += '0'
		return m1


class Solution:

	def digitsNum(self, N):
		ans = ''
		NN = N
		while N > 0:
			t = min(9, N)
			ans = str(t) + ans
			N = N - 9
		return ans + '0' * NN


class Solution:

	def digitsNum(self, N):
		sr = ''
		k = N
		while N >= 9:
			sr = sr + '9'
			N = N - 9
		else:
			sr = sr + str(N)
		return int(sr[::-1]) * 10 ** k


class Solution:

	def digitsNum(self, N):
		sol = ''
		k = N
		while N > 0:
			temp = min(9, N)
			sol = str(temp) + sol + '0' * temp
			N = N - 9
		return sol


class Solution:

	def digitsNum(self, N):
		(m, a, c) = (N, 0, 1)
		while m != 0:
			if m >= 9:
				a = 10 * a + 9
				m -= 9
				c *= 10
			else:
				a += c * m
				m = 0
		return a * 10 ** N


class Solution:

	def digitsNum(self, N):
		c = 0
		l = N
		while N > 9:
			c += 1
			N -= 9
		k = ''
		for i in range(c):
			k += '9'
		for i in range(l):
			k += '0'
		m = str(N) + k
		return m


class Solution:

	def digitsNum(self, N):
		s = ''
		if N % 9 != 0:
			s = s + str(N % 9)
		for i in range(1, N // 9 + 1):
			s += '9'
		for i in range(1, N + 1):
			s += '0'
		return s


class Solution:

	def digitsNum(self, N):
		s = ''
		n = N
		while n:
			for i in range(9, -1, -1):
				if n - i >= 0:
					s += str(i)
					n -= i
					break
		s = s[::-1]
		s += '0' * N
		return int(s)


from math import *

class Solution:

	def digitsNum(self, N):
		s = ''
		k = N
		while N != 0:
			if N < 10:
				s = str(N) + s
				N = 0
			else:
				s = str(9) + s
				N -= 9
		return int(s) * 10 ** k


class Solution:

	def digitsNum(self, n):
		ans = ''
		if n % 9 != 0:
			ans += str(n % 9)
		p = n // 9
		for i in range(0, p):
			ans += '9'
		for i in range(0, n):
			ans += '0'
		return ans


class Solution:

	def digitsNum(self, N):
		n = N
		if N < 10:
			return N * 10 ** N
		s = 0
		r = 0
		while N > 9:
			N = N - 9
			s = s * 10 + 9
			r += 1
		a = N * 10 ** r + s
		return a * 10 ** n


class Solution:

	def digitsNum(self, N):
		s = ''
		num = N
		while num > 0:
			if num >= 9:
				num -= 9
				s = '9' + s
			else:
				s = str(num) + s
				num -= num
		return s + '0' * N


class Solution:

	def digitsNum(self, n):
		re = ''
		if n <= 9:
			re = str(n)
		else:
			a = n // 9
			b = n % 9
			c = '9' * a
			if b > 0:
				re = str(b) + c
			else:
				re = c
		k = '0' * n
		return re + k


class Solution:

	def digitsNum(self, N):
		l = []
		if N == 0:
			l.append(0)
		if N % 9 != 0:
			l.append(N % 9)
		for i in range(1, int(N / 9) + 1):
			l.append(9)
		for i in range(1, N + 1):
			l.append(0)
		res = ''
		for i in l:
			res += str(i)
		return int(res)


class Solution:

	def digitsNum(self, N):
		if N == 0:
			print('0', end='')
		str1 = ''
		if N % 9 != 0:
			str1 += str(N % 9)
		for i in range(1, int(N / 9) + 1):
			str1 = str1 + str('9')
		for i in range(1, N + 1):
			str1 = str1 + str('0')
		return str1


class Solution:

	def digitsNum(self, N):
		num = N % 9
		for _ in range(int(N / 9)):
			num = num * 10 + 9
		for _ in range(N):
			num *= 10
		return num


class Solution:

	def digitsNum(self, N):
		res = str(N % 9) if N % 9 else ''
		return res + '9' * (N // 9) + '0' * N


class Solution:

	def digitsNum(self, N):
		div_pow = 10 ** N
		if N < 10:
			return N * div_pow
		else:
			s = ''
			nine = '9'
			rem = N % 9
			dt = N - rem
			times = int(dt / 9)
			s = str(rem) + str(9) * times
			return int(s) * div_pow


class Solution:

	def digitsNum(self, N):
		n = N
		l = []
		while n != 0:
			if n <= 9:
				l.append(str(n))
				n = 0
			else:
				l.append('9')
				n -= 9
		return int(''.join(l[::-1])) * 10 ** N


class Solution:

	def digitsNum(self, N):
		ans = ''
		if N == 0:
			ans += '0'
			return ans
		if N % 9 != 0:
			ans += chr(N % 9 + ord('0'))
		for i in range(1, N // 9 + 1):
			ans += '9'
		for i in range(1, N + 1):
			ans += '0'
		return ans


class Solution:

	def digitsNum(self, N):
		return int(str(N % 9) + '9' * (N // 9)) * pow(10, N)


class Solution:

	def digitsNum(self, N):
		a = N % 9
		b = (N - a) // 9
		c = a * 10 ** b
		d = 0
		for i in range(0, b):
			d += 9 * 10 ** i
		e = c + d
		f = e * 10 ** N
		return f


class Solution:

	def digitsNum(self, N):
		K = N
		res = ''
		while K > 9:
			res += '9'
			K -= 9
		res += str(K)
		res = res[::-1]
		for i in range(N):
			res += '0'
		return int(res)


class Solution:

	def digitsNum(self, N):
		result = [str(N % 9)]
		result += ['9'] * (N // 9)
		result += ['0'] * N
		return int(''.join(result))


class Solution:

	def digitsNum(self, N):
		if N < 10:
			return N * 10 ** N
		s = ''
		s += str(N % 9)
		for i in range(N // 9):
			s += '9'
		return int(s) * 10 ** N


class Solution:

	def digitsNum(self, N):
		if N < 10:
			return N * 10 ** N
		n9 = N // 9
		st = str(n % 9) + str('9') * n9 + str('0') * N
		s = int(st)
		return s


class Solution:

	def digitsNum(self, N):
		ans = []
		if N < 10:
			ans.append(str(N))
			ans += ['0'] * N
		elif N >= 10:
			nines = N // 9
			rem = N % 9
			if rem != 0:
				ans.append(str(rem))
			ans += ['9'] * nines
			ans += ['0'] * N
		return ''.join(ans)


class Solution:

	def digitsNum(self, N):
		if n >= 10:
			nums = []
			for k in range(1, 10):
				n_nines = (N - k) // 9
				add_val = str(N - k - n_nines * 9)
				if add_val == '0':
					add_val = ''
				num = str(k) + (N - k) // 9 * '9' + add_val
				nums.append(int(num))
			ret_val = str(sorted(nums)[0]) + '0' * N
		else:
			ret_val = str(N) + '0' * N
		ret_val = int(ret_val)
		return ret_val


class Solution:

	def digitsNum(self, N):
		a = N % 9
		b = (N - a) // 9
		s = ''
		if a != 0:
			s += str(a)
		for i in range(b):
			s += '9'
		for i in range(N):
			s += '0'
		return s


class Solution:

	def digitsNum(self, N):
		count = ''
		if N == 0:
			return 0
		elif N <= 9:
			return N * 10 ** N
		elif N >= 9:
			for i in range(N):
				N = N - 9
				count = count + str(9)
				if N <= 9:
					count = count + str(N)
					break
				elif N == 9:
					count = count + str(N)
					break
				elif N >= 9:
					pass
		count = count[::-1]
		p = sum([int(x) for x in count])
		return count + '0' * p


class Solution:

	def digitsNum(self, N):
		l = ''
		Sum = N
		while Sum > 0:
			if Sum > 9:
				l += '9'
			else:
				l += str(Sum)
			Sum -= 9
		l1 = l[::-1]
		for i in range(N):
			l1 += '0'
		return l1


class Solution:

	def digitsNum(self, N):
		k = ''
		t = N
		while N > 0:
			if N < 10:
				k = str(N) + k
				N = 0
			else:
				k = k + '9'
				N = N - 9
		p = int(k)
		return p * 10 ** t


class Solution:

	def digitsNum(self, N):
		t = N % 9
		l = [9] * (N // 9)
		if t != 0:
			l.append(t)
		res = 0
		for i in range(len(l)):
			res += l[i] * 10 ** i
		return res * 10 ** N


class Solution:

	def digitsNum(self, N):
		if N <= 9:
			p = N
		else:
			r = N // 9
			d = N - r * 9
			for i in range(r):
				d = d * 10 + 9
			p = d
		return p * pow(10, N)


class Solution:

	def digitsNum(self, N):
		m = N
		x = ''
		while N >= 9:
			x += '9'
			N -= 9
		if N > 0:
			x += str(N)
		x = x[::-1]
		x += '0' * m
		return x


class Solution:

	def digitsNum(self, N):
		if N > 9:
			r = N % 9
			d = N // 9
			s = str(r)
			for i in range(d):
				s = s + '9'
		else:
			s = str(N)
		for j in range(N):
			s = s + '0'
		return int(s)


class Solution:

	def digitsNum(self, N):
		qwe = 10 ** N
		a = ''
		while N > 9:
			N -= 9
			a = a + '9'
		a = int(str(N) + a)
		f = a * qwe
		return f


class Solution:

	def digitsNum(self, N):
		P = N
		number = ''
		while N > 0:
			if N > 9:
				number = str(9) + number
				N = N - 9
			else:
				number = str(N) + number
				N = 0
		return int(number) * 10 ** P


class Solution:

	def digitsNum(self, N):
		num = '0' * N
		a = str(N % 9)
		b = N // 9 * '9'
		return int(a + b + num)


class Solution:

	def digitsNum(self, n):
		s = str(n % 9 or '')
		s += '9' * (n // 9)
		s += '0' * n
		return s


class Solution:

	def digitsNum(self, N):
		if n < 10:
			return n * 10 ** N
		else:
			d = N // 9
			r = N % 9
			return ((r + 1) * 10 ** d - 1) * 10 ** N


class Solution:

	def digitsNum(self, n):
		x = ''
		i = n
		while i > 0:
			if i > 9:
				x += '9'
			else:
				x += str(i)
			i -= 9
		return x[::-1] + '0' * n


class Solution:

	def digitsNum(self, N):
		s = N
		a = ''
		while s > 0:
			if s > 9:
				a += '9'
			else:
				a += str(s)
			s -= 9
		ans = a[::-1]
		for i in range(N):
			ans += '0'
		return ans


class Solution:

	def digitsNum(self, N):
		res = '0' * N
		(q, r) = divmod(N, 9)
		return (str(r) + '9' * q + res).lstrip('0')


class Solution:

	def digitsNum(self, N):
		l = ['0'] * N
		s = ''
		while N >= 10:
			l.insert(0, '9')
			N -= 9
		l.insert(0, str(N))
		return s.join(l)


class Solution:

	def digitsNum(self, N):
		t = N
		s = ''
		while N > 0:
			a = min(N, 9)
			s = s + str(a)
			N -= 9
		return int(s[::-1]) * 10 ** t


class Solution:

	def digitsNum(self, N):
		n = ''
		temp = N
		x = 9
		num = 10 ** N
		while temp not in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
			n = '9' + n
			temp = temp - x
		y = str(temp)
		n = y + n
		n = int(n)
		return n * num


class Solution:

	def digitsNum(self, N):
		ans = '0' * N
		while N > 9:
			ans = '9' + ans
			N -= 9
		ans = str(N) + ans
		return int(ans)


class Solution:

	def digitsNum(self, N):
		s = ''
		for i in range(N):
			s = s + '0'
		while N > 0:
			temp = 0
			if N > 9:
				s = '9' + s
				temp = 9
			else:
				s = str(N) + s
				temp = N
			N = N - temp
		return s


import math

class Solution:

	def digitsNum(self, N):
		s = N % 9
		for i in range(0, N // 9):
			s = s * 10 + 9
		for i in range(0, N):
			s = s * 10
		return int(s)


class Solution:

	def digitsNum(self, N):
		j = 0
		Power = N
		res = 0
		while N > 0:
			temp = min(9, N)
			res += temp * 10 ** j
			N = N - 9
			j += 1
		return res * 10 ** Power


class Solution:

	def digitsNum(self, N):
		s = ''
		for i in range(N):
			s += str('0')
		while True:
			if N > 9:
				s += str(9)
				N -= 9
			elif N == 0:
				break
			else:
				s += str(N)
				break
		return s[::-1]


class Solution:

	def digitsNum(self, N):
		prefix = ''
		N1 = N
		while N1:
			if N1 > 9:
				N1 -= 9
				prefix = str(9) + prefix
			else:
				prefix = str(N1) + prefix
				break
		return int(prefix) * 10 ** N


class Solution:

	def digitsNum(self, N):
		y = 10 ** N
		i = N
		r = N % 9
		q = N // 9
		s = ''
		for i in range(q):
			s = s + '9'
		s = str(r) + s
		s = int(s)
		return s * y


class Solution:

	def digitsNum(self, N):
		n_left = N
		s = ''
		while n_left > 0:
			nd = min(n_left, 9)
			s = str(nd) + s
			n_left -= nd
		return int(s) * 10 ** N


class Solution:

	def digitsNum(self, N):
		if N <= 9:
			return N * 10 ** N
		c = 0
		M = N
		while N >= 9:
			N = N - 9
			c += 1
		r = str(N) + '9' * c
		return int(r) * 10 ** M


class Solution:

	def digitsNum(self, N):
		ANS = ''
		if N == 0:
			return N
		elif N % 9 != 0:
			ANS += str(N % 9)
			for i in range(1, N // 9 + 1):
				ANS += '9'
			for j in range(1, N + 1):
				ANS += '0'
			return ANS
		else:
			for i in range(1, N // 9 + 1):
				ANS += '9'
			for i in range(1, N + 1):
				ANS += '0'
			return ANS


class Solution:

	def digitsNum(self, N):
		n = N
		lst = list()
		res = n - 9
		while res > 0:
			lst.append(9)
			n -= 9
			res = n - 9
		lst.append(n)
		return int(''.join(map(str, reversed(lst)))) * 10 ** N


class Solution:

	def digitsNum(self, N):
		s = ''
		num = N
		while N > 0:
			temp = min(9, N)
			s = str(temp) + s + '0' * temp
			N -= 9
		return s


class Solution:

	def digitsNum(self, N):
		str1 = ''
		while N > 0:
			x = min(9, N)
			str1 = str(x) + str1 + '0' * x
			N = N - 9
		return str1


class Solution:

	def digitsNum(self, N):
		x = n
		y = n
		ans = 0
		while x > 9:
			ans += 1
			x -= 9
		while ans > 0:
			x = x * 10 + 9
			ans -= 1
		while y > 0:
			x = x * 10
			y -= 1
		return x