Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'.
Example 1:
Input: N = 2, S = 9
Output: 90
Explaination: It is the biggest number 
with sum of digits equals to 9.
Example 2:
Input: N = 3, S = 20
Output: 992
Explaination: It is the biggest number 
with sum of digits equals to 20.
Your Task:
You do not need to read input or print anything. Your task is to complete the function findLargest() which takes N and S as input parameters and returns the largest possible number. Return -1 if no such number is possible.
Expected Time Complexity: O(N)
Exepcted Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{4}
0 ≤ S ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def findLargest(self, N, S):
        # code here

Solutions:
class Solution:

	def findLargest(self, N, S):
		if S == 0:
			if N == 1:
				return 0
			else:
				return -1
		else:
			nineArray = [0] * N
			for i in range(N):
				if S > 9:
					nineArray[i] = 9
					S = S - 9
				else:
					nineArray[i] = S
					S = 0
			if S > 0 and i >= N - 1:
				return -1
			res = int(''.join(map(str, nineArray)))
			return res


class Solution:

	def findLargest(self, N, S):
		l = []
		c = 0
		s = S
		while c < N:
			if s >= 9:
				l.append(9)
				s -= 9
			else:
				x = s
				l.append(x)
				s -= x
			c += 1
		if N * 9 < S:
			return -1
		elif N > 1 and S == 0:
			return -1
		elif S == 0 and N == 1:
			return 0
		else:
			ans = ''
			for i in l:
				ans += str(i)
			return ans


class Solution:

	def findLargest(self, N, S):
		if S == 0:
			if N == 1:
				return 0
			return -1
		digits = [i for i in range(9, -1, -1)]
		result = 0
		sums = 0
		for i in range(N):
			for d in digits:
				if sums + d <= S:
					result *= 10
					result += d
					sums += d
					break
		if sums == S:
			return result
		return -1


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N == 1:
			return 0
		if S == 0 and N > 1:
			return -1
		if N * 9 < S:
			return -1
		m = 9
		s = ''
		c = 0
		while c < N:
			if S >= m:
				s += str(m)
				S -= m
				c += 1
			else:
				m -= 1
		return s


class Solution:

	def findLargest(self, N, S):
		if S <= 9 and N == 1:
			return S
		elif S > 0 and S <= 9 and (N > 1):
			return S * 10 ** (N - 1)
		ans = S
		dgt = 9
		i = 1
		S -= 9
		N -= 1
		SUM = 9
		while N > 0:
			if S >= 9:
				dgt = dgt * 10
				dgt += 9
				SUM += 9
				S = S - 9
			elif S < 0:
				return -1
			else:
				dgt = dgt * 10
				dgt += S
				SUM += S
				break
			N -= 1
		if SUM != ans:
			return -1
		if N > 0:
			return dgt * 10 ** (N - 1)
		return dgt


class Solution:

	def findLargest(self, N, S):
		ans = ''
		if S == 0 and N == 1:
			return 0
		if S == 0 and N > 1:
			return -1
		if N * 9 < S:
			return -1
		count = 0
		a = 9
		while count < N:
			if S >= a:
				ans += str(a)
				S -= a
				count += 1
			else:
				a -= 1
		return ans


class Solution:

	def findLargest(self, N, S):
		if S <= 9 and N == 1:
			return S
		elif S > 0 and S <= 9 and (N > 1):
			return S * 10 ** (N - 1)
		ans = S
		su = 9
		i = 1
		S -= 9
		N -= 1
		sum = 9
		while N > 0:
			if S >= 9:
				su = su * 10
				su += 9
				sum += 9
				S = S - 9
			elif S < 0:
				return -1
			else:
				su = su * 10
				su += S
				sum += S
				break
			N -= 1
		if sum != ans:
			return -1
		if N > 0:
			return su * 10 ** (N - 1)
		return su


class Solution:

	def findLargest(self, N, S):
		if N * 9 < S or (N > 1 and S == 0):
			return -1
		int_pos = '9' * (S // 9)
		N -= S // 9
		S = S % 9
		if S != 0:
			int_pos += str(S)
			N -= 1
		int_pos += N * '0'
		return int_pos


class Solution:

	def findLargest(self, N, S):
		s = ['0' for i in range(N)]
		if S == 0:
			if N > 1:
				return -1
			return 0
		if S <= 9:
			s[0] = str(S)
			return ''.join(s)
		i = 0
		while S > 9 and i < N:
			s[i] = '9'
			S = S - 9
			i = i + 1
			if i < N and S <= 9:
				s[i] = str(S)
				return ''.join(s)
		return -1


class Solution:

	def findLargest(self, N, S):
		n = ''
		while N:
			for i in range(9, 0, -1):
				if S - i >= 0:
					n += str(i)
					S -= i
					break
			else:
				n += str(0)
			N -= 1
		if int(n) == 0 and len(n) > 1 or S > 0:
			return -1
		else:
			return n


class Solution:

	def findLargest(self, n, s):
		if n == 1 and s == 0:
			return 0
		if s // 9 > n or (s // 9 == n and s % 9 != 0) or (s == 0 and n != 0):
			return -1
		k = s // 9
		t = k * '9'
		if n - k > 0:
			t += str(s - k * 9)
		if n - k - 1 > 0:
			t += (n - k - 1) * '0'
		return t


class Solution:

	def findLargest(self, N, S):
		x = S // 9
		if 9 * N < S or (S == 0 and N > 1):
			return -1
		else:
			r = S % 9
			cnt = x
			s = ''
			for i in range(x):
				s += '9'
			if r != 0:
				s += str(r)
				cnt += 1
			if cnt < N:
				s += '0' * (N - cnt)
		return s


class Solution:

	def findLargest(self, N, S):
		if S > 9 * N or (N > 1 and S < 1):
			return -1
		if N == 1 and S == 0:
			return 0
		num = ''
		i = 1
		while i <= N:
			if S >= 9:
				num += '9'
				S -= 9
			elif S > 0 and S < 9:
				num += str(S)
				S = 0
			else:
				num += '0'
			i += 1
		return num


class Solution:

	def findLargest(self, N, S):
		sum_ = S
		s = ''
		n = N
		if S == 0 and N > 1:
			return -1
		while n > 0 and sum_ >= 0:
			if sum_ - 9 >= 0:
				s = s + '9'
				n -= 1
				sum_ = sum_ - 9
			elif sum_ < 9:
				s = s + str(sum_)
				n -= 1
				sum_ = 0
		while n > 0:
			s = s + '0'
		x = 0
		for i in range(len(s)):
			x = x + int(s[i])
		if S > x:
			return -1
		return s


class Solution:

	def findLargest(self, N, S):
		if S == 0:
			if N == 1:
				return 0
			return -1
		if 9 * N < S:
			return -1
		res = ''
		while S >= 9:
			S -= 9
			res += '9'
			N -= 1
		if N == 0:
			return res
		res += str(S)
		N -= 1
		while N > 0:
			res += '0'
			N -= 1
		return res


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N != 1:
			return -1
		a = ''
		while N > 0:
			if S >= 9:
				a += '9'
				S -= 9
			elif S < 9:
				a += str(S)
				S = 0
			N -= 1
		if S != 0:
			return -1
		return int(a)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N > 1:
			return -1
		ans = 0
		for _ in range(N):
			if S >= 9:
				ans = ans * 10 + 9
				S -= 9
			else:
				ans = ans * 10 + S
				S = 0
		return ans if S == 0 else -1


class Solution:

	def findLargest(self, N, S):
		str_num = ''
		while S >= 9:
			str_num += '9'
			S -= 9
		if S > 0:
			str_num += str(S)
		if len(str_num) > N or (len(str_num) == 0 and N > 1):
			return -1
		else:
			str_num += '0' * (N - len(str_num))
			return int(str_num)


class Solution:

	def findLargest(self, N, S):
		ans = [0] * N
		osum = S
		if S == 0:
			if N <= 1:
				return 0
			else:
				return -1
		else:
			for i in range(N):
				if S >= 9:
					ans[i] = 9
					S -= 9
				else:
					ans[i] = S
					S = 0
		if sum(ans) == osum:
			ans = ''.join(map(str, ans))
		else:
			ans = -1
		return ans


class Solution:

	def findLargest(self, N, S):
		if S == 0:
			if N == 1:
				return 0
			else:
				return -1
		num = ''
		curr_sum = S
		for i in range(N):
			if curr_sum > 9:
				curr_sum -= 9
				num += '9'
			elif curr_sum > 0:
				num += str(curr_sum)
				curr_sum -= curr_sum
			elif curr_sum == 0:
				num += '0'
		if curr_sum is not 0:
			return -1
		return int(num)


class Solution:

	def findLargest(self, N, S):
		if S <= 0 and N != 1:
			return -1
		ans = ''
		i = 0
		while i < N:
			if S >= 9:
				ans += '9'
				S -= 9
			elif S >= 0:
				new = str(S)
				ans += new
				S = 0
			i += 1
		if S > 0:
			return -1
		return int(ans)


class Solution:

	def findLargest(self, N, S):
		ans = ''
		if S == 0:
			if N == 1:
				return '0'
			else:
				return '-1'
		if S > N * 9:
			return '-1'
		for i in range(N):
			if S >= 9:
				ans += '9'
				S -= 9
			else:
				ans += str(S)
				S = 0
		return ans


class Solution:

	def findLargest(self, N, S):
		if 9 * N < S:
			return -1
		elif S == 0:
			if N == 1:
				return 0
			return -1
		res = []
		for digit in range(9, -1, -1):
			count = S // digit
			if count > 0:
				res += [str(digit)] * count
				S -= digit * count
				break
		if S > 0:
			res.append(str(S))
		if len(res) < N:
			res += ['0'] * (N - len(res))
		return ''.join(res)


class Solution:

	def findLargest(self, N, S):
		if S > 9 * N or (S == 0 and N > 1):
			return -1
		if S < 10:
			return str(S) + '0' * (N - 1)
		i = 9
		ans = ''
		while S > 0:
			ans += S // i * str(i)
			S %= i
			i -= 1
		return ans + (N - len(ans)) * '0'


class Solution:

	def findLargest(self, N, S):
		if S == 0:
			if N == 1:
				temp = 0
			else:
				temp = -1
		elif S > N * 9:
			temp = -1
		else:
			temp = 0
			for i in range(N):
				if S >= 9:
					temp = temp * 10 + 9
					S = S - 9
				else:
					temp = temp * 10 + S
					S = 0
		return temp


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N > 1:
			return -1
		if 9 * N < S:
			return -1
		qt = S // 9
		if qt == N:
			return '9' * qt
		rem = S % 9
		nzero = N - (qt + 1)
		ans = '9' * qt + str(rem) + '0' * nzero
		return ans


class Solution:

	def findLargest(self, N, S):
		if N == 1 and S < 10:
			return str(S)
		if S == 0 or S > N * 9:
			return '-1'
		num = ''
		for i in range(N):
			if S >= 9:
				num += '9'
				S -= 9
			elif S > 0:
				num += str(S)
				S = 0
			else:
				num += '0'
		return num


class Solution:

	def findLargest(self, N, S):
		temp = 10 ** (N - 1)
		no = 9
		res = 0
		if no * N < S:
			return -1
		if S == 0 and N != 1:
			return -1
		while S:
			if S < no:
				no -= 1
			else:
				res += no * temp
				temp //= 10
				S -= no
		return res


class Solution:

	def findLargest(self, N, S):
		res = [0] * N
		if S <= 0 and N > 1:
			return -1
		elif S <= 0 and N == 1:
			return 0
		elif S > N * 9:
			return -1
		for i in range(N):
			if S >= 9:
				res[i] = 9
				S -= 9
			else:
				res[i] = S
				S = 0
		f = [str(i) for i in res]
		result = int(''.join(f))
		return result


class Solution:

	def findLargest(self, n, s):
		r = 0
		for i in range(1, n + 1):
			if s >= 9:
				r = r * 10 + 9
				s -= 9
			else:
				r = r * 10 + s
				s = 0
		if len(str(r)) < n or s > 0:
			return -1
		return r


class Solution:

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


class Solution:

	def findLargest(self, m, s):
		ans = ''
		if s == 0:
			if m == 1:
				return 0
			else:
				return -1
		if s > 9 * m:
			return -1
		for i in range(m):
			if s >= 9:
				ans += str(9)
				s -= 9
			else:
				ans += str(s)
				s = 0
		return int(ans)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N == 1:
			return 0
		if S == 0 or S > 9 * N:
			return -1
		number = []
		for i in range(N):
			digit = min(9, S)
			S -= digit
			number.append(str(digit))
		return ''.join(number)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N != 1:
			return -1
		st = ''
		while N > 0:
			if S >= 9:
				st += '9'
				S -= 9
				N -= 1
			elif S < 9 and S > 0:
				st += str(S)
				S = 0
				N -= 1
			else:
				st += '0'
				N -= 1
		if S != 0:
			return -1
		return st


class Solution:

	def findLargest(self, N, s):
		ans = 0
		if s == 0 and N != 1:
			return -1
		while N > 0:
			if s >= 9:
				ans = ans * 10 + 9
				s -= 9
			elif s < 9:
				ans = ans * 10 + s
				s = 0
			N -= 1
		if s != 0:
			return -1
		return ans


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N > 1:
			return -1
		if 9 * N < S:
			return -1
		t = S // 9
		if S % 9 == 0:
			return str('9') * t + '0' * (N - t)
		return str('9') * t + str(S % 9) + '0' * (N - t - 1)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N == 1:
			return 0
		elif S == 0 and N != 1:
			return -1
		s = ''
		for i in range(N):
			if S >= 9:
				s += '9'
				S -= 9
			elif S < 9 and S > 0:
				s += str(S)
				S -= S
			else:
				s += '0'
		if S == 0:
			return int(s)
		else:
			return -1


class Solution:

	def findLargest(self, N, S):
		if N > 1 and S == 0 or N * 9 < S:
			return -1
		s = S
		tot = ''
		res = [0 for i in range(N + 1)]
		for i in range(0, N - 1):
			if s > 9:
				res[i] = 9
				s -= 9
			else:
				res[i] = s
				s = 0
		res[N - 1] = s
		for i in range(N):
			tot += str(res[i])
		return tot


class Solution:

	def findLargest(self, N, S):
		ans = 0
		temp = S
		if S == 0 and N > 1:
			return -1
		cnt = 0
		while cnt < N:
			if S >= 9:
				ans = ans * 10 + 9
				S -= 9
			else:
				ans = ans * 10 + S
				S = 0
			cnt += 1
		return ans if S == 0 else -1


class Solution:

	def findLargest(self, N, S):
		if N * 9 < S:
			return '-1'
		elif S == 0:
			if N == 1:
				return '0'
			else:
				return '-1'
		else:
			a = S // 9
			b = S % 9
			if b != 0:
				ans = a * '9' + str(b)
			else:
				ans = a * '9'
			k = N - len(ans)
			ans += '0' * k
			return ans


class Solution:

	def findLargest(self, N, S):
		num = []
		sum = 0
		if S == 0 and N > 1:
			return -1
		for i in range(N):
			num.append('9')
			sum += 9
		if sum == S:
			return ''.join(num)
		c = sum - S
		if c < 0:
			return -1
		for j in range(1, N + 1):
			if c <= 9:
				num[-j] = str(9 - c)
				return ''.join(num)
			else:
				num[-j] = str(0)
				c -= 9
			if c == 0:
				return ''.join(num)


class Solution:

	def findLargest(self, N, S):
		num = [0 for x in range(N)]
		ind = 0
		if 9 * N < S or (S == 0 and N > 1):
			return -1
		while S > 9:
			num[ind] += 9
			ind += 1
			S -= 9
		else:
			num[ind] = S
		res = list(map(str, num))
		return int(''.join(res))


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N > 1:
			return -1
		res = ''
		res += '9' * (S // 9)
		res += str(S % 9) if S % 9 else ''
		if len(res) < N:
			res += '0' * (N - len(res))
			return res
		elif len(res) == N:
			return res
		return -1


class Solution:

	def findLargest(self, N, S):
		if S > N * 9:
			return -1
		if S == 0 and N > 1:
			return -1
		a = 9
		c = 0
		sol = 0
		if S <= a:
			return S * 10 ** (N - 1)
		else:
			while a > 0:
				if S - a < 0:
					a -= 1
				else:
					sol = sol * 10 + a
					S = S - a
					c += 1
			return sol * 10 ** (N - c)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N != 1:
			return -1
		if S == 0 and N == 1:
			return 0
		s = ''
		check = 9
		k = N
		while N > 0:
			while check != 0:
				if check <= S:
					s = s + str(check)
					S = S - check
					break
				else:
					check -= 1
			if check == 0:
				break
			N -= 1
		if S != 0:
			return -1
		c = k - len(s)
		while c > 0:
			s = s + '0'
			c -= 1
		return s


import itertools as its

class Solution:

	def findLargest(self, N, S):
		if S == 0 and N > 1:
			return -1
		ans = 0
		for _ in range(N):
			if S >= 9:
				ans = ans * 10 + 9
				S -= 9
			else:
				ans = ans * 10 + S
				S = 0
		return ans if S == 0 else -1


class Solution:

	def findLargest(self, N, S):
		st = ''
		for i in range(N):
			for j in range(9, -1, -1):
				if S - j >= 0:
					st += str(j)
					S -= j
					break
		if S != 0:
			return -1
		st = int(st)
		if len(str(st)) != N:
			return -1
		return st


class Solution:

	def findLargest(self, N, S):
		z = S // 9
		if S == 0:
			if N > 1:
				return -1
			else:
				return 0
		elif z == N:
			if S % 9 != 0:
				return -1
			else:
				return int('9' * N)
		elif z > N:
			return -1
		else:
			return int('9' * z + str(S % 9) + '0' * (N - z - 1))


class Solution:

	def findLargest(self, N, S):
		if 9 * N < S or (N > 1 and S == 0):
			return -1
		sum = S
		position = 0
		number = 0
		first_position = [9, 8, 7, 6, 5, 4, 3, 2, 1]
		rest_position = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
		while position != N:
			if position == 0:
				for i in first_position:
					if sum - i >= 0:
						number = 10 * number + i
						sum = sum - i
						break
			else:
				for i in rest_position:
					if sum - i >= 0:
						number = 10 * number + i
						sum = sum - i
						break
			position += 1
		return number


class Solution:

	def findLargest(self, N, S):
		Ans = ''
		if S == 0 and N == 1:
			return 0
		elif S == 0 and N > 1:
			return -1
		for i in range(N):
			temp = 9
			while temp > S:
				temp -= 1
			S -= temp
			Ans += str(temp)
		if S > 0:
			return -1
		return int(Ans)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N != 1:
			return -1
		ans = ''
		for x in range(N):
			if S >= 9:
				ans += '9'
				S -= 9
			else:
				ans += str(S)
				S -= S
		if S == 0:
			return int(ans)
		return -1


class Solution:

	def findLargest(self, N, s):
		if s > N * 9:
			return -1
		n = N
		s1 = ''
		while n > 0:
			if s >= 9:
				s1 += '9'
				s -= 9
			else:
				s1 += str(s)
				s = 0
			n -= 1
		return -1 if int(s1) == 0 and N > 1 else s1


class Solution:

	def findLargest(self, N, S):
		if N > 1 and S == 0:
			return -1
		if S > 9 * N:
			return -1
		number = ''
		divide = S // 9
		reminder = S % 9
		for i in range(divide):
			number += '9'
		if reminder > 0:
			number = number + str(reminder)
			N -= 1
		i = N - divide - 1
		while i >= 0:
			number += '0'
			i -= 1
		return int(number)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N > 1:
			return -1
		if 9 * N < S:
			return -1
		l = ''
		c = 0
		while S > 0:
			if S - 9 >= 0:
				S = S - 9
				c += 1
				l += '9'
			else:
				c += 1
				l += str(S)
				break
		x = N - len(l)
		for i in range(x):
			l += '0'
		return int(l)


def largestPossible(n, s):
	if s == 0 and n > 1:
		return -1
	a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	a = a[::-1]
	text = ''
	while s > 0:
		for num in a:
			if num <= s:
				text += str(num)
				s -= num
				break
	if len(text) < n:
		text += '0' * (n - len(text))
	if len(text) > n:
		return -1
	return text

class Solution:

	def findLargest(self, N, S):
		return largestPossible(N, S)


class Solution:

	def findLargest(self, N, S):
		if S == 0 and N > 1:
			return -1
		result = 0
		for i in range(N):
			if S >= 9:
				result = result * 10 + 9
				S -= 9
			else:
				result = result * 10 + S
				S = 0
		return result if S == 0 else -1


class Solution:

	def findLargest(self, N, S):
		self.x = 9
		self.temp = ''
		if S == 0 and N > 1:
			return -1
		while N > 0 and self.x >= 0:
			if S - self.x > -1:
				self.temp += str(self.x)
				S -= self.x
				N -= 1
			if S >= self.x:
				continue
			else:
				self.x -= 1
		if S != 0:
			return -1
		else:
			return self.temp


class Solution:

	def findLargest(self, N, S):
		val = S
		ans = ''
		f = False
		for i in range(N):
			temp = 0
			for j in range(9, -1, -1):
				if val >= j:
					f = True
					temp = j
					break
			ans += str(temp)
			val -= temp
		if int(ans) == 0 and len(ans) > 2 or val > 0:
			return -1
		if f:
			return ans
		return -1