The task is to find the smallest number with given sum of digits as S and number of digits as D.
 
Example 1:
Input:
S = 9 
D = 2
Output:
18
Explanation:
18 is the smallest number
possible with sum = 9
and total digits = 2.
 
Example 2:
Input:
S = 20
D = 3
Output:
299
Explanation:
299 is the smallest number
possible with sum = 20
and total digits = 3.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function smallestNumber() which takes the two integers S and D and returns a string which is the smallest number if possible, else return "-1".
 
Expected Time Complexity: O(D)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ S ≤ 100
1 ≤ D ≤ 6

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms
Expected Time Complexity: O(D)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:
    def smallestNumber (self, S, D):
        # code here 


Solutions:
class Solution:

	def smallestNumber(self, S, D):
		if S > 9 * D:
			return '-1'
		S = S - 1
		i = D - 1
		res = [''] * D
		while i >= 0:
			if S >= 10:
				res[i] = str(9)
				i -= 1
				S -= 9
			elif i != 0:
				res[i] = str(S)
				i -= 1
				S = 0
			else:
				res[i] = str(S + 1)
				break
		return ''.join(res)


class Solution:

	def smallestNumber(self, S, D):
		k = ''
		if S <= 9 * D:
			S -= 1
			for i in range(D - 1):
				if S > 9:
					k += '9'
					S -= 9
				else:
					k += str(S)
					S -= S
			val = 1 + S
			k += str(val)
			return k[::-1]
		return -1


class Solution:

	def smallestNumber(self, S, D):
		ans = ''
		if S > D * 9:
			return -1
		for i in range(D - 1, -1, -1):
			if S > 9:
				ans = '9' + ans
				S -= 9
			elif i == 0:
				ans = str(S) + ans
			else:
				ans = str(S - 1) + ans
				i -= 1
				while i > 0:
					ans = '0' + ans
					i -= 1
				ans = '1' + ans
				break
		return ans if ans else -1


class Solution:

	def smallestNumber(self, S, D):
		if S == 0:
			if D == 1:
				return S
		if D * 9 < S:
			return -1
		S = S - 1
		res = ''
		for i in range(D - 1):
			if S > 9:
				res = '9' + res
				S = S - 9
			else:
				res = str(S) + res
				S = 0
		res = str(S + 1) + res
		return res


class Solution:

	def get_num_sum(self, num):
		ans = 0
		while num:
			ans += num % 10
			num = num // 10
		return ans

	def smallestNumber(self, S, D):
		for i in range(10 ** (D - 1), 10 ** D):
			if self.get_num_sum(i) == S:
				return i
		return -1


class Solution:

	def smallestNumber(self, S, D):
		(s, d) = (S, D)
		if 9 * d < s:
			return -1
		res = ''
		for i in range(d - 1, -1, -1):
			if s > 9:
				res = '9' + res
				s -= 9
			elif i == 0:
				res = str(s) + res
			else:
				res = str(s - 1) + res
				i -= 1
				while i > 0:
					res = '0' + res
					i -= 1
				res = '1' + res
				break
		return res


import math

def smallest_number_util(curr_sum: int, number: str, sum_need: int, digits: int):
	for i in reversed(range(0, digits)):
		if int(number[i]) == 0 or int(number[i]) == 1:
			remaining_sum = sum_need - curr_sum
			if remaining_sum >= 10:
				number_list = list(number)
				number_list[i] = str(9)
				curr_sum = curr_sum + 9
				number = ''.join(number_list)
				return smallest_number_util(curr_sum, number, sum_need, digits)
			else:
				number_list = list(number)
				value = int(number[i]) + remaining_sum
				number_list[i] = str(value)
				return ''.join(number_list)
		if int(number[i]) == 9:
			continue
	return '-1'

def smallest_number(sum_value: int, digits: int):
	max_sum = 9 * digits
	if sum_value > max_sum:
		return '-1'
	curr_sum = 1
	number = str(int(math.pow(10, digits - 1)))
	return smallest_number_util(curr_sum, number, sum_value, digits)

class Solution:

	def smallestNumber(self, S, D):
		return smallest_number(S, D)


class Solution:

	def smallestNumber(self, S, D):
		if 9 * D < S:
			return -1
		sum = S - 1
		i = 0
		ans = ''
		while i < D - 1:
			if sum >= 9:
				ans = '9' + ans
				sum -= 9
			else:
				ans = str(sum) + ans
				sum -= sum
			i += 1
		ans = str(sum + 1) + ans
		return int(ans)


class Solution:

	def smallestNumber(self, S, D):
		ans = 10 ** (D - 1)
		S -= 1
		place = 1
		digit = 1
		while S > 0:
			if digit == D:
				if S > 8:
					return -1
				else:
					ans += place * S
					S = 0
			elif S > 9:
				ans += place * 9
				S -= 9
			else:
				ans += place * S
				S = 0
			place *= 10
			digit += 1
		return ans


class Solution:

	def smallestNumber(self, S, D):
		if S == 0 or D == 0 or S > D * 9:
			return -1
		ans = ''
		for i in range(D):
			if ans == '':
				ans += '1'
				S -= 1
			else:
				ans += '0'
		num = ''
		i = 0
		while i < S:
			if ans[-1] == '9':
				num += '9'
				ans = ans[:-1]
			else:
				ans = int(ans)
				ans += 1
				i += 1
				ans = str(ans)
		num = ans + num
		return num


class Solution:

	def smallestNumber(self, S, D):
		if S == 0:
			if D == 1:
				print(' smallest possible is', S)
			return
		if S > 9 * D:
			return -1
		res = ''
		S = S - 1
		for i in range(0, D - 1):
			if S > 9:
				res = '9' + res
				S = S - 9
			else:
				res = str(S) + res
				S = 0
		res = str(S + 1) + res
		return res


class Solution:

	def smallestNumber(self, S, D):
		if S > 9 * D:
			return '-1'
		nums = [1]
		S = S - 1
		D = D - 1
		num1 = []
		while D > 0 and S > 0:
			if S >= 9:
				num1.append(9)
				S -= 9
			else:
				num1.append(S)
				S = 0
			D -= 1
		if S != 0:
			num1.append(S + 1)
			num1.sort()
			return ''.join(map(str, num1))
		while D > 0:
			num1.append(0)
			D -= 1
		num1.sort()
		nums.extend(num1)
		return ''.join(map(str, nums))


class Solution:

	def smallestNumber(self, S, D):
		if 9 * D < S:
			return -1
		ans = ''
		while D > 0 and S > 0:
			if S > 9:
				ans += '9'
				S -= 9
				D -= 1
			else:
				if D > 1:
					ans += str(S - 1)
					S = 1
					D -= 1
				elif D == 1:
					ans += str(S)
					D -= 1
					S = 0
				while D > 1:
					ans += '0'
					D -= 1
				if D == 1:
					ans += str(S)
					S -= 1
					D -= 1
		return ans[::-1]


class Solution:

	def smallestNumber(self, s, d):
		l = []
		if s > 9 and d == 1:
			return '-1'
		for i in range(d - 1):
			l.append(0)
		l.append(1)
		s = s - sum(l)
		div = s // 9
		rem = s % 9
		if s < 9:
			l[0] = l[0] + s
		else:
			if div > d:
				return '-1'
			for i in range(div):
				l[i] = l[i] + 9
				c = i
			if rem > 0 and c + 1 > len(l) - 1:
				return '-1'
			if rem > 0:
				l[c + 1] = l[c + 1] + rem
		l = l[::-1]
		for i in range(len(l)):
			l[i] = str(l[i])
		x = ''.join(l)
		return x


class Solution:

	def smallestNumber(self, S, D):
		if D * 9 < S:
			return -1
		new = [None] * D
		for i in range(D - 1, 0, -1):
			if S > 9:
				new[i] = 9
				S -= 9
			elif S <= 9:
				new[i] = S - 1
				S = 1
		new[0] = S
		num = 0
		for i in new:
			num = num * 10 + i
		return num


class Solution:

	def smallestNumber(self, S, D):
		if S > 9 * D:
			return -1
		i = D
		result = 0
		Diff = 9 * D - S
		while i >= 1:
			if Diff < 9:
				temp = 9 - Diff
				temp = temp * 10 ** (i - 1)
				result += temp
				Diff -= Diff
			elif i == D:
				temp = 9 - 8
				temp = temp * 10 ** (i - 1)
				result += temp
				Diff -= 8
			else:
				temp = 9 - 9
				temp = temp * 10 ** (i - 1)
				result += temp
				Diff -= 9
			i -= 1
		return result


class Solution:

	def smallestNumber(self, S, D):
		if S > D * 9:
			return -1
		small = [1]
		for _ in range(D - 1):
			small.append(0)
		s = S - 1
		for j in range(len(small) - 1, -1, -1):
			if j == 0:
				small[j] += s
			elif s > 9:
				small[j] = 9
				s -= 9
			else:
				small[j] = s
				break
		ans = small[0]
		for i in range(1, len(small)):
			ans *= 10
			ans += small[i]
		return ans


class Solution:

	def smallestNumber(self, S, D):
		if 9 * D < S:
			return -1
		if D == 1:
			return S
		if S <= 9:
			s = str(S - 1)
			s += '0' * (D - 2)
			s += '1'
		elif S % 9 == 0:
			s = '9' * (S // 9 - 1)
			s += '8'
			D -= len(s)
			s += '0' * (D - 1)
			s += '1'
		else:
			s = '9' * (S // 9)
			D -= len(s)
			if D >= 2:
				s += str(S % 9 - 1)
				s += '0' * (D - 2)
				s += '1'
			else:
				s += str(S % 9)
		return int(s[::-1])


class Solution:

	def smallestNumber(self, S, N):
		if N > 1 and S > 0:
			S -= 1
		s = ''
		if S > N * 9:
			return -1
		if S <= 9 and N == 1:
			return S
		while N > 1:
			N -= 1
			if S > 9:
				s += '9'
				S -= 9
			else:
				s += str(S)
				S -= S
		s += str(S + 1)
		return int(s[::-1])


class Solution:

	def smallestNumber(self, S, D):
		if S > 9 * D:
			return '-1'
		ans = []
		while D > 0:
			if S >= 9:
				ans.append(9)
				S -= 9
			elif S > 0:
				ans.append(S)
				S = 0
			elif S == 0:
				ans[-1] -= 1
				ans.append(1)
			D -= 1
		res = ''
		for i in ans[::-1]:
			res += str(i)
		return res


class Solution:

	def smallestNumber(self, S, D):
		s = ''
		for i in range(D):
			for j in range(9, -1, -1):
				if i < D - 1 and S - j > 0:
					s += str(j)
					S -= j
					break
				elif i == D - 1 and S - j == 0:
					s += str(j)
					S -= j
					break
		if S != 0:
			return '-1'
		s = s[::-1]
		return int(s)


class Solution:

	def smallestNumber(self, s, d):
		ans = ''
		i = d - 1
		if 9 * d < s:
			return -1
		while i >= 0:
			if s > 9:
				ans = '9' + ans
				s -= 9
			elif i == 0:
				ans = str(s) + ans
			else:
				ans = str(s - 1) + ans
				i -= 1
				while i > 0:
					ans = '0' + ans
					i -= 1
				ans = '1' + ans
			i -= 1
		return ans


class Solution:

	def smallestNumber(self, S, D):
		ans = 0
		if S == 0:
			if D == 1:
				return 0
			else:
				return -1
		if S > 9 * D:
			return -1
		ls = [0] * D
		S -= 1
		for i in range(D - 1, 0, -1):
			if S > 9:
				ls[i] = 9
				S -= 9
			else:
				ls[i] = S
				S = 0
		ls[0] = S + 1
		ls = [str(ls[i]) for i in range(D)]
		return int(''.join(ls))


class Solution:

	def smallestNumber(self, S, D):
		sum = S
		digit = D
		res = ''
		if S > 9 * D:
			return -1
		while digit > 0:
			digit -= 1
			aval = sum - 1 if digit != 0 else sum
			number = 9 if aval > 9 else aval
			res = str(number) + res
			sum -= number
		return res


class Solution:

	def smallestNumber(self, S, D):
		ans = ''
		if D * 9 < S:
			return -1
		S = S - 1
		curr_sum = 0
		for j in range(D - 1):
			for i in range(9, -1, -1):
				if curr_sum + i <= S:
					ans = str(i) + ans
					curr_sum += i
					flag = 1
					break
		msb = S + 1 - curr_sum
		ans = str(msb) + ans
		return int(ans)


class Solution:

	def smallestNumber(self, s, d):
		res = 0
		dc = d
		while dc > 0:
			f = False
			for i in range(10):
				if i == 0 and dc == d:
					continue
				rem = s - i
				if rem <= (dc - 1) * 9:
					res = res * 10 + i
					s -= i
					f = True
					break
			if not f:
				return -1
			dc -= 1
		return res


class Solution:

	def smallestNumber(self, S, D):
		if S == 0:
			if m == 1:
				return 0
			else:
				return -1
		if S > 9 * D:
			return -1
		S = S - 1
		s = ''
		ans = [0 for i in range(D + 1)]
		for i in range(D - 1, 0, -1):
			if S > 9:
				ans[i] = 9
				S -= 9
			else:
				ans[i] = S
				S = 0
		ans[0] = S + 1
		s = ''
		for i in ans:
			s += str(i)
		s = s[:len(s) - 1]
		a = int(s)
		return a


class Solution:

	def smallestNumber(self, S, D):
		if S < 1:
			return -1
		res = [0] * D
		S -= 1
		res[-1] = 1
		for i in range(D):
			res[i] += min(9, S)
			S -= min(9, S)
			S = max(S, 0)
		if S > 0 or res[-1] > 9:
			return -1
		st = ''
		for i in res:
			st = str(i) + st
		return st


class Solution:

	def smallestNumber(self, S, D):
		result = ''
		while S > 9:
			result = '9' + result
			S -= 9
		if len(result) >= D:
			return -1
		if len(result) == D - 1:
			return str(S) + result
		result = str(S - 1) + result
		while len(result) < D - 1:
			result = '0' + result
		return '1' + result


class Solution:

	def smallestNumber(self, S, D):
		if 9 * D < S:
			return -1
		ans = 0
		while D:
			d = max(0, S - (D - 1) * 9)
			if d == 0 and ans == 0:
				d = 1
			ans = ans * 10 + d
			S -= d
			D -= 1
		return ans


class Solution:

	def smallestNumber(self, S, D):
		if D * 9 < S:
			return -1
		ans = ''
		while True:
			if S > 9:
				ans = '9' + ans
				S -= 9
			else:
				if len(ans) == D - 1:
					ans = str(S) + ans
				else:
					ans = str(S - 1) + ans
					i = 1
					n = D - len(ans)
					while i < n:
						ans = '0' + ans
						i += 1
					ans = '1' + ans
				break
		return ans


class Solution:

	def smallestNumber(self, s, d):
		if 9 * d < s:
			return '-1'
		ans = ''
		for i in range(d - 1, -1, -1):
			if s > 9:
				ans = '9' + ans
				s -= 9
			elif i == 0:
				ans = str(s) + ans
			else:
				ans = str(s - 1) + ans
				i -= 1
				while i > 0:
					ans = '0' + ans
					i -= 1
				ans = '1' + ans
				break
		return ans


class Solution:

	def smallestNumber(self, S, D):
		if S > D * 9:
			return '-1'
		S -= 1
		res = 10 ** (D - 1)
		d = 1
		while S > 0:
			res += d * min(S, 9)
			S -= min(S, 9)
			d *= 10
		return str(res)


class Solution:

	def smallestNumber(self, S, D):
		if S > D * 9:
			return -1
		num = 10 ** (D - 1)
		if S == 1:
			return num
		else:
			S -= 1
			t = 0
			while S // 10 > 0:
				num += 9 * 10 ** t
				S -= 9
				t += 1
			num += S * 10 ** t
			return num


class Solution:

	def smallestNumber(self, S, D):
		if S > 9 * D:
			return '-1'
		output = ''
		nines = min(D, (S - 1) // 9)
		for i in range(nines):
			output += '9'
		S -= nines * 9
		D -= nines
		if S == 0:
			return output
		if D == 1:
			return str(S) + output
		if D == 2:
			return str(1) + str(S - 1) + output
		zeros = ''
		for i in range(D - 2):
			zeros += '0'
		return str(1) + zeros + str(S - 1) + output


class Solution:

	def smallestNumber(self, S, D):
		if D * 9 < S:
			return -1
		if D == 1:
			return S
		ans = []
		if S > (D - 1) * 9:
			temp = S - (D - 1) * 9
			ans.append(temp)
			S -= temp
		else:
			ans.append(1)
			S -= 1
		ans += [0] * (D - 1)
		for i in range(D - 1, 0, -1):
			if S >= 9:
				ans[i] = 9
				S -= 9
			else:
				ans[i] = S
				S = 0
				break
		return ''.join([str(i) for i in ans])


class Solution:

	def smallestNumber(self, S, D):
		if 9 * D < S:
			return -1
		if D == 1:
			return str(S)
		arr = [0] * D
		arr[0] = 1
		S -= 1
		while D > 0:
			if S >= 9:
				arr[D - 1] = 9
				S -= 9
			else:
				arr[D - 1] += S
				break
			D -= 1
		return ''.join((str(x) for x in arr))


class Solution:

	def sum_of_digits(n):
		s = 0
		while n > 0:
			rem = n % 10
			s += rem
			n = n // 10
		return s

	def smallestNumber(self, S, D):
		for i in range(10 ** (D - 1), 10 ** D):
			if Solution.sum_of_digits(i) == S:
				return i
				break
		return -1


class Solution:

	def smallestNumber(self, s, d):
		if s == 0:
			if d == 1:
				return 0
			else:
				return -1
		if s > 9 * d:
			return -1
		s -= 1
		res = [0 for i in range(d)]
		for i in range(d - 1, 0, -1):
			if s > 9:
				res[i] = 9
				s -= 9
			else:
				res[i] = s
				s = 0
		res[0] = s + 1
		s = ''
		for i in res:
			s += str(i)
		return s


class Solution:

	def smallestNumber(self, S, D):
		s = S
		d = D
		l = []
		if S > 9 * D:
			return -1
		for i in range(D):
			if i != D - 1:
				if s > 9:
					s -= 9
					l.append('9')
				elif s == 1:
					l.append('0')
				else:
					l.append(str(s - 1))
					s = 1
			else:
				l.append(str(s))
		return ''.join(l[::-1])


class Solution:

	def smallestNumber(self, S, D):
		if 9 * D < S:
			return -1
		res = []
		j = D - 1
		while j > 0:
			for i in range(9, -1, -1):
				if S >= i and S - i != 0:
					res.append(i)
					S -= i
					break
			j -= 1
		if S > 9:
			return -1
		else:
			res.append(S)
		num = 0
		for i in range(len(res)):
			num += 10 ** i * res[i]
		return num


class Solution:

	def smallestNumber(self, S, D):
		if D > 0 and S == 0:
			return -1
		if S > D * 9:
			return -1
		ans = ''
		rem = D
		for i in range(D):
			if i > 0 and S <= rem * 9 - 9:
				ans += '0'
			elif S <= rem * 9 - 8:
				ans += '1'
				S = S - 1
			elif S < rem * 9:
				x = S % 9
				if x == 0:
					x = 9
				S = S - x
				ans += str(x)
			else:
				ans += '9'
				S = S - 9
			rem -= 1
		return ans


class Solution:

	def smallestNumber(self, S, D):
		target = S
		resp = [0] * D
		idx = D - 1
		while S > 9 and idx >= 0:
			resp[idx] = 9
			S -= 9
			idx -= 1
		if idx > 0:
			resp[idx] = S - 1
			S = 1
		resp[0] = S
		if sum(resp) == target:
			resp = list(map(str, resp))
			return int(''.join(resp))
		else:
			return -1


class Solution:

	def getSum(self, n):
		sum = 0
		while n != 0:
			sum = sum + n % 10
			n = n // 10
		return sum

	def smallestNumber(self, S, D):
		if D == 0:
			return -1
		if S == 0:
			if D == 1:
				return 0
			else:
				return -1
		if S > 9 * D:
			return -1
		ans = [0 for i in range(D)]
		S -= 1
		for i in range(D - 1, 0, -1):
			if S > 9:
				ans[i] = 9
				S -= 9
			else:
				ans[i] = S
				S = 0
		ans[0] = S + 1
		s = [str(i) for i in ans]
		res = int(''.join(s))
		return res


class Solution:

	def smallestNumber(self, S, D):
		if D == 0 or S > 9 * D:
			return -1
		digit = [0 for i in range(D)]
		Sum = S - 1
		digit[0] = 1
		for i in range(D - 1, 0, -1):
			if Sum > 9:
				digit[i] = 9
				Sum -= 9
			else:
				digit[i] = Sum
				Sum = 0
				break
		if Sum:
			digit[0] += Sum
		return int(''.join(list(map(str, digit))))


class Solution:

	def smallestNumber(self, S, D):

		def sma(m, s):
			if s > 9 * m:
				return -1
			if m == 0 and s > 0:
				return -1
			l = [0 for i in range(m)]
			s -= 1
			for i in range(m - 1, 0, -1):
				if s > 9:
					l[i] = '9'
					s -= 9
				else:
					l[i] = str(s)
					s -= s
			l[0] = str(s + 1)
			return ''.join(l)
		return sma(D, S)


class Solution:

	def smallestNumber(self, S, D):
		ans = ''
		uffer = (S - 1) // 9
		rest = S - 1 - uffer * 9
		for i in range(D - uffer - 1):
			if i == 0:
				ans += '1'
				continue
			ans += '0'
		for i in range(uffer + 1):
			if i == 0:
				if D - uffer - 1 <= 0:
					ans += str(rest + 1)
				else:
					ans += str(rest)
				continue
			ans += '9'
		if len(ans) != D:
			return '-1'
		return ans


class Solution:

	def smallestNumber(self, S, D):
		if S > D * 9:
			return '-1'
		res = [0 for i in range(D)]
		S = S - 1
		i = D - 1
		while S:
			if S > 9:
				res[i] = 9
				S -= 9
				i -= 1
			else:
				res[i] = S
				S = 0
		res[0] += 1
		ans = res[0]
		for i in range(1, D):
			ans = 10 * ans + res[i]
		return ans


class Solution:

	def smallestNumber(self, S, D):
		num = [0] * D
		num[0] = 1
		end = D - 1
		S = S - 1
		if D * 9 < S:
			return -1
		while S > 0:
			if S < 9:
				num[end] = num[end] + S
				S = 0
			else:
				num[end] = num[end] + 9
				end = end - 1
				S = S - 9
		string = ''
		for i in range(D):
			string = string + str(num[i])
		return string