The task is to find the second smallest number with a given sum of digits as S and the number of digits as D.
Example 1:
Input:
S = 9 
D = 2
Output:
27
Explanation:
18 is the smallest number possible with sum = 9
and total digits = 2, Whereas the second
smallest is 27.
Example 2:
Input:
S = 16
D = 3
Output:
178
Explanation:
169 is the smallest number possible with sum is
16 and total digits = 3, Whereas the second
smallest is 178.
Your Task:
You don't need to read input or print anything. Your task is to complete the function secondSmallest() which takes the two integers S and D respectively and returns a string which is the second smallest number if possible, else return "-1".
Expected Time Complexity: O(D)
Expected Space Complexity: O(1)
Constraints:
1 ≤ S ≤ 10^{5}
1 ≤ D ≤ 10^{5}

Difficulty: MEDIUM
Tags: Mathematics

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 secondSmallest(self, S, D):

        # code here 

Solutions:
class Solution:

	def secondSmallest(self, S, D):
		if S <= 9 and D == 1:
			return S
		if S >= 9 * D:
			return -1
		ret = []
		while S:
			if S >= 9:
				ret.append(9)
				S -= 9
			else:
				ret.append(S)
				S = 0
		if len(ret) < D:
			ret[-1] -= 1
			while len(ret) < D:
				ret.append(0)
			ret[-1] += 1
		for i in range(D):
			if ret[i] != 9:
				if i >= 1:
					ret[i] += 1
					ret[i - 1] -= 1
				else:
					ret[i] -= 1
					ret[i + 1] += 1
				break
		return int(''.join(map(str, ret[::-1])))


class Solution:

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


class Solution:

	def secondSmallest(self, S, D):
		if D == 1 and S <= 9:
			return S
		if S == 1 or S >= D * 9:
			return -1
		sumthing = [0 for i in range(D)]
		for i in range(D):
			if i == 0:
				assign = max(1, S - (D - 1 - i) * 9)
			else:
				assign = max(0, S - (D - 1 - i) * 9)
			sumthing[i] = assign
			S -= assign
		out = ''
		swap = False
		for i in range(D - 1, -1, -1):
			if not swap and i > 0 and (sumthing[i - 1] < 9):
				sumthing[i] -= 1
				sumthing[i - 1] += 1
				swap = True
			out = str(sumthing[i]) + out
		return out


class Solution:

	def secondSmallest(self, S, D):
		if S / 9 > D:
			return -1
		if S == 1:
			return -1
		if S / 9 == D:
			return -1
		if D == 1:
			return S
		i = D - 1
		curr = S
		ans = [0 for _ in range(D)]
		nines = 0
		while curr > 1:
			if curr > 9:
				ans[i] = 9
				curr -= 9
				nines += 1
			else:
				ans[i] = curr - 1
				curr = 1
			i -= 1
		ans[0] += 1
		ans[D - nines] += 9
		for i in range(D - nines, 0, -1):
			remainder = ans[i] % 10
			carry = ans[i] // 10
			ans[i] = remainder
			ans[i - 1] += carry
		if ans[0] > 9:
			return -1
		return ''.join((str(x) for x in ans))


class Solution:

	def secondSmallest(self, s, d):
		if s == 1 or d * 9 <= s:
			return '-1'
		ans = [1]
		for i in range(1, d):
			ans.append(0)
		s -= 1
		for i in range(d - 1, -1, -1):
			if s > 9:
				s -= 9
				ans[i] = 9
			else:
				ans[i] += s
				s = 0
				break
		for i in range(d - 1, -1, -1):
			if ans[i - 1] == 9:
				continue
			else:
				ans[i - 1] += 1
				ans[i] -= 1
				break
		res = ''
		for i in ans:
			res += str(i)
		return res


class Solution:

	def secondSmallest(self, s, d):
		if s >= 9 * d or s == 1:
			return -1
		a = [0 for i in range(d)]
		a[0] = 1
		s = s - 1
		i = d - 1
		while i >= 0 and s > 0:
			if s >= 9:
				a[i] += 9
				s -= 9
			else:
				a[i] += s
				break
			i -= 1
		(i, j) = (d - 1, d - 2)
		while j >= 0:
			if a[i] == a[j] == 9:
				i -= 1
				j -= 1
			else:
				break
		a[j] += 1
		a[i] -= 1
		ans = ''
		for i in a:
			ans += str(i)
		return int(ans)


class Solution:

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


class Solution:

	def secondSmallest(self, S, D):
		if S >= D * 9:
			return '-1'
		if S <= 9 and D == 1:
			return str(S)
		if D == 1 and S >= 10:
			return '-1'
		dup = D
		S -= 1
		ans = ''
		for i in range(D - 1, 0, -1):
			if S > 9:
				ans += str(9)
				S -= 9
			else:
				ans += str(S)
				S = 0
		ans += str(S + 1)
		ans = ans[::-1]
		ind = dup - 1
		for i in range(dup - 1, -1, -1):
			if ans[i] == '9':
				ind = i
			else:
				break
		ans = list(ans)
		ans[ind] = str(int(ans[ind]) - 1)
		ans[ind - 1] = str(int(ans[ind - 1]) + 1)
		ans = ''.join(ans)
		return ans


class Solution:

	def secondSmallest(self, S, D):
		if S >= D * 9:
			return -1
		if S <= 9 and D == 1:
			return S
		S -= 1
		ans = []
		while D:
			if S >= 9:
				ans += [9]
				S -= 9
			else:
				ans += [S]
				S = 0
			D -= 1
		ans[-1] += 1
		ans.reverse()
		n = len(ans)
		for i in range(n - 2, -1, -1):
			if ans[i] < 9:
				ans[i] += 1
				ans[i + 1] -= 1
				break
		return ''.join([str(i) for i in ans])


class Solution:

	def secondSmallest(self, S, D):
		if D == 1:
			if S < 10:
				return S
		num = [0 for i in range(D)]
		for i in range(D - 1, 0, -1):
			num[i] = min(S - 1, 9)
			S -= num[i]
		if S > 9:
			return -1
		num[0] = S
		change = 0
		for i in range(D - 1, 0, -1):
			if num[i] > 0 and num[i - 1] < 9:
				num[i] -= 1
				num[i - 1] += 1
				change = 1
				n = [str(i) for i in num]
				return ''.join(n)
		return -1


class Solution:

	def secondSmallest(self, S, D):
		d = [0] * D
		if S >= 9 * D:
			return -1
		if D == 1:
			return S
		d[0] = 1
		S -= 1
		count = 0
		for i in range(D - 1, -1, -1):
			if S > 0:
				if S < 9:
					d[i] += S
				else:
					d[i] = 9
					count += 1
				S -= 9
			else:
				break
		var = ''
		for j in d:
			var += str(j)
		if count == 0 or count == 1:
			t = int(var) + 9
		else:
			t = int(var) + 9 * pow(10, count - 1)
		return t


class Solution:

	def secondSmallest(self, S, D):
		num = S
		tot = D
		s = num - 1
		flag = 0
		num1 = []
		if num < 9 and tot == 1:
			return num
		if num >= tot * 9:
			return -1
		else:
			for i in range(tot - 1, 0, -1):
				if s >= 9:
					num1.append('9')
					s -= 9
				else:
					num1.append(str(s))
					s -= s
			num1.append(str(1 + s))
			num1 = num1[::-1]
			for i in range(len(num1)):
				if num1[i] == '9':
					num1[i] = '8'
					num1[i - 1] = str(int(num1[i - 1]) + 1)
					flag = 1
					break
			if flag == 1:
				ans = ''.join(num1)
				ans = int(ans)
			else:
				ans = ''.join(num1)
				ans = int(ans) + 9
			return ans


class Solution:

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


class Solution:

	def secondSmallest(self, S, D):
		temp = [None] * D
		su = S
		if S >= D * 9:
			return '-1'
		if D == 1:
			return -1
		for i in range(D - 1, 0, -1):
			d = min(su - 1, 9)
			temp[i] = d
			su -= d
		temp[0] = su
		i = D - 1
		while i > 0:
			if temp[i] != 0 and temp[i - 1] != 9:
				temp[i] -= 1
				temp[i - 1] += 1
				return ''.join((str(i) for i in temp))
			i -= 1
		return '-1'


class Solution:

	def secondSmallest(self, S, D):
		t = 9 * D
		if S >= t or D == 1:
			return -1
		else:
			a = [9 for i in range(D)]
			rem = 9 * D - S
			j = 0
			if rem <= 8:
				a[0] = a[0] - rem + 1
				a[1] = a[1] - 1
			else:
				a[0] = a[0] - 8
				rem = rem - 8
				j = j + 1
				while rem > 0 and j < D:
					if rem <= 9:
						a[j] = a[j] - rem
						rem = 0
					else:
						a[j] = a[j] - 9
						rem = rem - 9
						j = j + 1
				if j == D - 1:
					a[j - 1] = a[j - 1] + 1
					a[j] = a[j] - 1
				else:
					a[j] = a[j] + 1
					a[j + 1] = a[j + 1] - 1
		ans = ''
		for k in a:
			ans = ans + str(k)
		ansf = int(ans)
		return ansf


class Solution:

	def secondSmallest(self, S, D):
		if S == 1 or D == 1:
			return -1
		digits = []
		for i in range(D):
			digits.append(0)
		digits[0] = 1
		index = D - 1
		S -= 1
		while S > 0:
			S -= 9
			if S >= 0:
				if index == 0:
					return -1
				digits[index] = 9
				index -= 1
			else:
				digits[index] += 9 + S
		if index != D - 1:
			index += 1
		digits[index] -= 1
		digits[index - 1] += 1
		if digits[index - 1] > 9:
			return -1
		result = ''
		for i in range(D):
			result += str(digits[i])
		return result


class Solution:

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


class Solution:

	def secondSmallest(self, S, D):
		st = ''
		if D * 9 <= S:
			return -1
		for i in range(D, 0, -1):
			if S == 1:
				if i == 1:
					st += '1'
				else:
					st += '0'
			elif S - 1 >= 9:
				st += '9'
				S -= 9
			elif i == 1:
				st += str(S)
			else:
				st += str(S - 1)
				S -= S - 1
		x = ''
		for i in range(D):
			if st[i + 1] != '9':
				x += str(int(st[i]) - 1)
				x += str(int(st[i + 1]) + 1)
				x += st[i + 2:]
				break
			x += st[i]
		return int(x[::-1])


class Solution:

	def secondSmallest(self, S, D):
		if S >= 9 * D:
			return -1
		count = 0
		result = [0] * D
		S -= 1
		for i in range(D - 1, 0, -1):
			if S > 9:
				result[i] = 9
				S -= 9
			else:
				result[i] = S
				S = 0
		result[0] = S + 1
		i = D - 1
		while result[i - 1] == 9 and result[i] == 9:
			i -= 1
		result[i - 1] += 1
		result[i] -= 1
		return ''.join((str(num) for num in result))


class Solution:

	def secondSmallest(self, s, d):
		if d == 1:
			return -1
		else:
			if d * 9 < s:
				return -1
			r = ''
			for i in range(d - 1, -1, -1):
				e = i * 9
				if e - s >= 0 and i == d - 1:
					r += '1'
					s -= 1
				elif e - s >= 0:
					r += '0'
				else:
					r += str(s - e)
					s -= s - e
			c = 0
			for i in range(len(r) - 1, -1, -1):
				if r[i] == '9':
					c += 1
				else:
					break
			if c == 0 or c == 1:
				result = int(r) + 9
			else:
				result = int(r) + 9 * 10 ** (c - 1)
			if len(str(result)) == d:
				return result
			else:
				return -1


class Solution:

	def secondSmallest(self, S, D):
		if S >= 9 * D:
			return '-1'
		num = [0] * D
		num[0] = 1
		S -= 1
		for i in range(D - 1, -1, -1):
			num[i] += min(S, 9)
			S -= min(S, 9)
			if S == 0:
				break
		for i in range(D - 2, -1, -1):
			if num[i] < num[i + 1]:
				num[i] += 1
				num[i + 1] -= 1
				return ''.join(list(map(str, num)))
		return '-1'


class Solution:

	def secondSmallest(self, S, D):
		l = []
		if S < 10 and D == 1:
			return -1
		if S >= 9 * D:
			return -1
		for i in range(1, D):
			if S > 9:
				l.append(9)
				S = S - 9
				continue
			if S <= 9:
				l.append(S - 1)
				S -= S - 1
		l.append(S)
		if l[0] == 8:
			l[0] -= 1
			l[1] += 1
		else:
			for (i, v) in enumerate(l):
				if v != 9:
					l[i] += 1
					l[i - 1] -= 1
					break
		l.reverse()
		s = ''
		for v in l:
			s += str(v)
		return s


class Solution:

	def secondSmallest(self, S, D):
		s = S
		st = ''
		if S >= 9 * D or D == 1 or S == 0:
			return -1
		d = D
		S -= 1
		for i in range(d - 1):
			if S > 9 and D > 1:
				S -= 9
				st += str(9)
				D -= 1
			else:
				st += str(S)
				S = 0
		st += str(S + 1)
		fin = st[::-1]
		ans = int(fin)
		new = 10 ** (s // 9 - 1)
		if s % 9 == 0 and new > 1:
			new /= 10
		if new <= 1:
			ans += 9
		else:
			ans += new * 9
		return int(ans)


class Solution:

	def secondSmallest(self, S, D):
		if D == 1 or S == 1:
			return -1
		k = S // 9
		if k >= D:
			return -1
		r = S % 9
		if r == 0:
			r = 9
			k -= 1
		if k == 0:
			return 1 * 10 ** (D - 1) + 10 + (r - 2)
		else:
			return 1 * 10 ** (D - 1) + r * 10 ** k + 9 * 10 ** (k - 1) - 1


class Solution:

	def secondSmallest(self, s, D):
		num = [None] * D
		for i in range(D - 1, 0, -1):
			d = min(s - 1, 9)
			num[i] = d
			s -= d
		if s > 9:
			return '-1'
		num[0] = s
		i = D - 1
		while i > 0:
			if num[i] != 0 and num[i - 1] != 9:
				num[i] -= 1
				num[i - 1] += 1
				return ''.join((str(x) for x in num))
			i -= 1
		return '-1'


class Solution:

	def secondSmallest(self, S, D):
		if S >= 9 * D:
			return -1
		ans = [0 for _ in range(D)]
		ans[0] = 1
		S -= 1
		for i in range(D - 1, -1, -1):
			if S == 0:
				break
			dif = min(S, 9 - ans[i])
			ans[i] += dif
			S -= dif
		found = False
		for i in range(D - 2, -1, -1):
			if ans[i] != 9:
				ans[i] += 1
				ans[i + 1] -= 1
				found = True
				break
		if not found:
			return -1
		res = ''
		for i in range(D):
			res += str(ans[i])
		return res


class Solution:

	def secondSmallest(self, s, d):
		if s == d or s == d * 9 or s > d * 9 or (s == 1):
			return -1
		ans = ''
		f = True
		while s:
			val = min(9, s - 1)
			ans += str(val)
			s -= val
			d -= 1
			if d == 1:
				ans += str(s)
				break
		res = ''
		seen = True
		pos = 0
		for i in ans:
			if i != '9':
				break
			pos += 1
		if pos:
			return (ans[:pos - 1] + str(int(ans[pos - 1]) - 1) + str(int(ans[pos]) + 1) + ans[pos + 1:])[::-1]
		return (ans[:pos] + str(int(ans[pos]) - 1) + str(int(ans[pos + 1]) + 1) + ans[pos + 2:])[::-1]


class Solution:

	def secondSmallest(self, S, D):
		minD = S // 9 + 1
		sum = S
		if D < minD:
			return -1
		digits = ''
		res = 0
		while S > 0:
			d = min(S, 9)
			S -= d
			digits = str(d) + digits
		n = len(digits)
		if n < D:
			if n < 2:
				return 2 * 10 + sum - 2
			else:
				digits = str(int(digits[0]) - 1) + digits[1:]
				res = 10 ** (D - 1) + int(str(int(digits[0]) + 1) + str(int(digits[1]) - 1) + digits[2:])
		elif n > 2:
			res = int(str(int(digits[0]) + 1) + str(int(digits[1]) - 1) + digits[2:])
		else:
			res = int(str(int(digits[0]) + 1) + str(int(digits[1]) - 1))
		return res


class Solution:

	def secondSmallest(self, S, D):
		if S >= D * 9 or D == 1:
			return -1
		arr = []
		while D > 1:
			if S == 1:
				arr.append(0)
			else:
				temp = min(9, S - 1)
				arr.append(temp)
				S -= temp
			D -= 1
		arr.append(S)
		if arr == [1, 1]:
			(arr[0], arr[1]) = (2, 0)
		else:
			for i in range(len(arr) - 1):
				if arr[i] > arr[i + 1]:
					arr[i] -= 1
					arr[i + 1] += 1
					break
		output = ''
		for n in arr:
			output += str(n)
		return output[::-1]


class Solution:

	def secondSmallest(self, S, D):
		if D == 1:
			return -1
		res = [0] * D
		res[0] = 1
		t = 1
		i = D - 1
		while t < S:
			t += 9 - res[i]
			res[i] = 9
			i -= 1
			if i == -1:
				break
		if t <= S and i == -1:
			return -1
		if t > S:
			i += 1
			res[i] -= t - S
		i = min(i, D - 2)
		res[i] += 1
		res[i + 1] -= 1
		return int(''.join((str(i) for i in res)))


class Solution:

	def secondSmallest(self, S, D):
		if S == D and D == 1:
			return -1
		if D * 9 <= S:
			return -1
		ans = ['0'] * D
		S -= 1
		ans[0] = '1'
		idx = -1
		while S:
			if S >= 9:
				ans[idx] = '9'
				S -= 9
			else:
				ans[idx] = str(int(ans[idx]) + S)
				S = 0
			idx -= 1
		for i in range(D - 1, 0, -1):
			if ans[i] != ans[i - 1]:
				ans[i] = str(int(ans[i]) - 1)
				ans[i - 1] = str(int(ans[i - 1]) + 1)
				break
		else:
			ans[1] = str(int(ans[1]) - 1)
			ans[0] = str(int(ans[0]) + 1)
		return int(''.join(ans))


class Solution:

	def secondSmallest(self, S, D):
		if D < 2 or 9 * D - 1 < S:
			return -1
		t = ''
		s = 0
		for i in range(1, 9):
			if (S - i) / (D - 1) <= 9.0:
				t = t + str(i)
				s = s + i
				break
		for i in range(2, D):
			f = 0
			j = 0
			while j < 10 and f == 0:
				if (S - s - j) / (D - i) <= 9.0:
					t = t + str(j)
					s += j
					f = 1
				j = j + 1
		t = t + str(S - s)
		if S < 18:
			t = str(int(t) + 9)
		elif S % 9 != 0:
			t = str(int(t) + 9 * pow(10, int(S / 9) - 1))
		else:
			t = str(int(t) + 9 * pow(10, int(S / 9) - 2))
		return t


class Solution:

	def secondSmallest(self, S, D):
		a = [0] * D
		a[0] = 1
		val = S - 1
		if S >= 9 * D:
			return -1
		for i in range(0, len(a)):
			a[-(i + 1)] += min(9, val)
			val -= a[-(i + 1)]
		for i in range(1, len(a)):
			if a[-i - 1] + 1 <= 9 and a[-i] - 1 >= 0:
				a[-i - 1] += 1
				a[-i] -= 1
				break
		return ''.join((str(num) for num in a))


class Solution:

	def secondSmallest(self, S, D):
		n = [0] * D
		n[D - 1] = min(S - 2, 8)
		if n[D - 1] == -1:
			return -1
		S -= n[D - 1]
		for j in reversed(range(1, D - 1)):
			if S - 1 > 9:
				n[j] = 8
				n[j + 1] = n[j + 1] + 1
				S -= 9
			else:
				c = max(0, min(S - 1, 9))
				S -= c
				n[j] = c
		if S < 10 and S > 0:
			n[0] = S
			return ''.join(map(str, n))
		return -1


class Solution:

	def smallest_num(self, S, D):
		s = S - 1
		d = D
		ss = ''
		no_9 = s // 9
		rem = s % 9
		if no_9 > 0:
			rem += 1
			ss = '9' * (no_9 - 1)
			ss = str(rem) + '8' + ss
		elif rem > 0:
			ss = str(1) + str(rem - 1)
		if len(ss) < D:
			ss = '0' * (D - len(ss)) + ss
		ss = str(int(ss[0]) + 1) + ss[1:len(ss)]
		return ss

	def secondSmallest(self, S, D):
		if S == 1 or S >= 9 * D or D == 1:
			return -1
		else:
			return self.smallest_num(S, D)


class Solution:

	def secondSmallest(self, S, D):
		ans = []
		if D == 1 or S == 1 or D * 9 <= S:
			return '-1'
		for i in range(0, D):
			if S > 9:
				ans.append('9')
				S -= 9
			elif S == 1:
				if i == D - 1:
					ans.append('1')
				else:
					ans.append('0')
			elif i == D - 1:
				ans.append(str(S))
			else:
				ans.append(str(S - 1))
				S = 1
		st = []
		ans = ans[::-1]
		for i in range(D - 2, -1, -1):
			if int(ans[i]) < int(ans[i + 1]):
				ans[i] = str(int(ans[i]) + 1)
				ans[i + 1] = str(int(ans[i + 1]) - 1)
				return ''.join(ans)


class Solution:

	def secondSmallest(self, S, D):
		if 9 * D < S:
			return -1
		S = S - 1
		ans = ''
		for i in range(D - 1, 0, -1):
			if S > 9:
				ans = '9' + ans
				S = S - 9
			elif i == 0:
				ans = str(S + 1) + ans
			else:
				ans = str(S) + ans
				S = 0
		ans = str(S + 1) + ans
		if int(10 ** D - 1) == int(ans):
			return -1
		l = list(ans)
		idx = D - 1
		for i in range(D - 1, 0, -1):
			if l[i] == '9':
				idx = i
			else:
				break
		l[idx] = str(int(l[idx]) - 1)
		l[idx - 1] = str(int(l[idx - 1]) + 1)
		ans = ''.join(l)
		return ans


class Solution:

	def secondSmallest(self, S, D):
		if S >= D * 9:
			return '-1'
		if D == 1:
			return str(S)
		a = ''
		temp = S - 1
		for i in range(D):
			if temp >= 9:
				a += '9'
				temp -= 9
			else:
				a += str(temp)
				temp = 0
		cnt = int(a[-1]) + 1
		a = a[:-1] + str(cnt)
		a = a[::-1]
		pre = a[-1]
		for i in range(len(a) - 2, -1, -1):
			if pre != a[i]:
				a = a[:i] + str(int(a[i]) + 1) + str(int(a[i + 1]) - 1) + a[i + 2:]
				break
		return a


class Solution:

	def secondSmallest(self, S, D):
		if D == 1 or S == 1 or S >= 9 * D:
			return '-1'
		isChanged = False
		sb = []
		for i in range(0, D):
			digit = 0
			if S > 9:
				digit = 9
				S -= 9
			elif i == D - 1:
				digit = S
			elif S > 1:
				digit = S - 1
				S = 1
			else:
				digit = 0
			if not isChanged and digit < 9 and (len(sb) > 0):
				digit += 1
				c = sb[len(sb) - 1]
				sb[len(sb) - 1] = c - 1
				isChanged = True
			sb.append(digit)
		s = ''
		for i in range(len(sb) - 1, -1, -1):
			s += str(sb[i])
		return s


class Solution:

	def sm_num(self, S, D):
		kll = S - 1
		ioo = ''
		nu = kll // 9
		rem = kll % 9
		if nu > 0:
			rem += 1
			ioo = (nu - 1) * '9'
			ioo = str(rem) + '8' + ioo
		elif rem > 0:
			ioo = str(1) + str(rem - 1)
		if len(ioo) < D:
			ioo = (D - len(ioo)) * '0' + ioo
		ioo = str(int(ioo[0]) + 1) + ioo[1:len(ioo)]
		return ioo

	def secondSmallest(self, S, D):
		if S == 1 or S >= 9 * D or D == 1:
			return -1
		else:
			return self.sm_num(S, D)


import sys

class Solution:

	def secondSmallest(self, S, D):
		if D < 2 or S < 2 or S > 9 * D - 1:
			return '-1'
		(q, r) = divmod(S, 9)
		digits = [9] * q + [r] + [0] * (D - 1 - q)
		lnz = q - (r == 0)
		digits[lnz] -= 1
		digits[-1] += 1
		if lnz == 0:
			lnz = 1
		digits[lnz] += 1
		digits[lnz - 1] -= 1
		return ''.join(map(str, reversed(digits)))


class Solution:

	def secondSmallest(self, s, d):
		if d * 9 <= s:
			return -1
		p = [1]
		for i in range(d - 1):
			p.append(0)
		s -= 1
		for i in range(d - 1, -1, -1):
			if s > 9:
				p[i] += 9
				s -= 9
			else:
				p[i] += s
				s = 0
		for i in range(d - 2, -1, -1):
			if p[i] != 9:
				p[i] += 1
				p[i + 1] -= 1
				break
		ans = ''
		for i in p:
			ans += str(i)
		return int(ans)


import sys

class Solution:

	def secondSmallest(self, S, D):
		if D * 9 <= S or D == 1 or S == 1:
			return '-1'
		num = [0] * D
		num[0] = 1
		S = S - 1
		for i in range(D - 1, 0, -1):
			if S > 9:
				num[i] = 9
				S = S - 9
			else:
				num[i] = S
				S = 0
		if S != 0:
			num[0] += S
		for i in range(D - 1, 0, -1):
			if num[i] <= 9 and num[i - 1] != 9:
				num[i - 1] += 1
				num[i] -= 1
				break
		s = ''
		for i in num:
			s += str(i)
		return s


class Solution:

	def secondSmallest(self, S, D):
		num = [0] * D
		for i in range(D - 1, 0, -1):
			d = min(S - 1, 9)
			num[i] = d
			S -= d
		if S > 9:
			return '-1'
		num[0] = S
		for i in range(D - 1, 0, -1):
			if num[i] != 0 and num[i - 1] != 9:
				num[i] -= 1
				num[i - 1] += 1
				return ''.join(map(str, num))
		return '-1'


class Solution:

	def secondSmallest(self, S, D):
		if D == 1 or S == 1:
			return '-1'
		ans = ['0'] * D
		ans[0] = '1'
		S -= 1
		i = D - 1
		while i > 0:
			if S > 9:
				ans[i] = '9'
				S -= 9
			else:
				ans[i] = str(S)
				S = 0
				break
			i -= 1
		if S > 7:
			return '-1'
		if S:
			ans[0] = str(S + 2)
			ans[1] = '8'
			return ''.join(ans)
		else:
			if ans[i] < '9':
				if i + 1 < D:
					ans[i] = str(int(ans[i]) + 1)
					ans[i + 1] = '8'
				else:
					ans[i - 1] = str(int(ans[i - 1]) + 1)
					ans[i] = str(int(ans[i]) - 1)
			else:
				ans[i - 1] = str(int(ans[i - 1]) + 1)
				ans[i] = str(int(ans[i]) - 1)
			return ''.join(ans)


class Solution:

	def secondSmallest(self, S, D):
		d = D
		arr = [0] * D
		arr[0] = 1
		s = 1
		while D > 0 and s != S:
			arr[D - 1] += min(S - s, 9)
			s += arr[D - 1]
			D -= 1
		arr = [str(i) for i in arr]
		temp = arr
		flag = True
		for i in range(len(temp) - 2, -1, -1):
			if int(temp[i]) < 9:
				temp[i] = int(temp[i]) + 1
				temp[i + 1] = int(temp[i + 1]) - 1
				flag = False
				break
		sex = int(''.join([str(i) for i in temp]))
		if len(str(sex)) > d or flag:
			return -1
		return sex