Geek lost the password of his super locker. He remembers the number of digits N as well as the sum S of all the digits of his password. He know that his password is the largest number of N digits that can be made with given sum S. As he is busy doing his homework, help him retrieving his password.
Example 1:
Input:
N = 5, S = 12
Output:
93000
Explanation:
Sum of elements is 12. Largest possible 
5 digit number is 93000 with sum 12.
Example 2:
Input:
N = 3, S = 29
Output:
-1
Explanation:
There is no such three digit number 
whose sum is 29.
Your Task : 
You don't need to read input or print anything. Your task is to complete the function largestNumber() which takes 2 integers N and S as input parameters and returns the password in the form of string, else return "-1" in the form of string.
Constraints:
1 ≤ N ≤ 10^{4}
0 ≤ S ≤ 9*10^{4}
Expected Time Complexity : O(N)
Expected Auxilliary Space : O(1)

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    #Function to return the largest possible number of n digits
    #with sum equal to given sum.
    def largestNum(self,n,s):
        
        # code here
    
    

Solutions:
class Solution:

	def largestNum(self, n, s):
		list = [0] * n
		nine = 9
		l = s
		for i in range(n):
			if nine <= l:
				list[i] = nine
				l -= nine
			else:
				list[i] = l
				l -= l
		if sum(list) != s:
			return -1
		ans = ''
		for i in list:
			ans += str(i)
		return ans


class Solution:

	def largestNum(self, n, s):
		d = [9, 8, 7, 6, 5, 4, 3, 2, 1]
		res = ''
		i = 0
		while i < len(d):
			if len(res) > n:
				break
			if d[i] <= s:
				res += str(d[i])
				s -= d[i]
			if d[i] > s:
				i += 1
			if s == 0:
				break
		if len(res) > n:
			return -1
		if len(res) < n:
			for j in range(len(res), n):
				res += '0'
		return res


class Solution:

	def largestNum(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 sum(l) != s:
			return -1
		ans = ''
		for i in l:
			ans += str(i)
		return ans


class Solution:

	def largestNum(self, n, s):
		if s > n * 9:
			return -1
		k = ''
		for i in range(n):
			if s == 0:
				k += '0'
			elif s < 10:
				k += str(s)
				s -= s
			else:
				k += '9'
				s -= 9
		return k


class Solution:

	def largestNum(self, n, s):
		arr = [0] * n
		for i in range(n):
			if s >= 9:
				arr[i] = 9
				s -= 9
			else:
				arr[i] = s
				s = 0
				break
		if s > 0:
			return -1
		arr = list(map(str, arr))
		final = ''.join(arr)
		return final


from itertools import combinations
from itertools import product

class Solution:

	def largestNum(self, n, s):
		lis = [0] * n
		k = 9
		l = s
		for i in range(n):
			if k <= l:
				lis[i] = k
				l = l - k
			else:
				lis[i] = l
				l -= l
		if sum(lis) == s:
			S = ''
			for i in range(n):
				S += str(lis[i])
			return S
		return -1
		return 0


class Solution:

	def largestNum(self, n, s):
		lis = [0] * n
		k = 9
		l = s
		for i in range(n):
			if k <= l:
				lis[i] = k
				l -= k
			else:
				lis[i] = l
				l -= l
		if sum(lis) != s:
			return -1
		ans = ''
		for i in lis:
			ans += str(i)
		return ans


class Solution:

	def largestNum(self, n, s):
		z = n * 9
		if z < s:
			return -1
		else:
			x1 = s // 9
			x2 = s % 9
			if x2 == 0:
				x3 = '9' * x1
			else:
				x3 = '9' * x1 + str(x2)
			for i in range(n - len(x3)):
				x3 += '0'
			return x3


class Solution:

	def largestNum(self, n, s):
		num9 = s // 9
		odigit = s % 9
		i = 0
		pas = 0
		num0 = n - (num9 + int(bool(odigit)))
		if s == 0:
			pas = str(pas).rjust(n, '0')
			return pas
		if num0 < 0:
			return -1
		while i < n:
			if i < num9:
				pas = pas * 10 + 9
			elif i == num9:
				pas = pas * 10 + odigit
			else:
				pas = pas * 10
			i += 1
		return pas


class Solution:

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


class Solution:

	def largestNum(self, n, s):
		arr = [0] * n
		sum = 0
		i = 0
		if s == 0:
			str1 = ''.join(map(str, arr))
			return str1
		while s > 0:
			if s >= 9 and i < n:
				arr[i] = 9
				s -= 9
				i += 1
			elif i >= n:
				break
			elif s < 9:
				arr[i] = s
				s = 0
				break
		if s != 0:
			return -1
		str1 = ''.join(map(str, arr))
		return str1


class Solution:

	def largestNum(self, n, s):
		nines = s // 9
		rem = s % 9
		co = nines
		an = '9' * nines
		if rem > 0:
			co += 1
			an += str(rem)
		if co > n:
			return -1
		an = an + '0' * (n - co)
		return an


class Solution:

	def largestNum(self, n, s):
		if 9 * n < s:
			return -1
		result = ''
		while s > 0:
			if s >= 9:
				result += str(9)
				s -= 9
			else:
				result += str(s)
				s = 0
		return result if len(result) == n else result + '0' * (n - len(result))


class Solution:

	def largestNum(self, n, s):
		l = [0] * n
		ni = 9
		ll = s
		for i in range(n):
			if ni <= ll:
				l[i] = ni
				ll -= ni
			else:
				l[i] = ll
				ll -= ll
		if sum(l) != s:
			return -1
		ans = ''
		for i in l:
			ans += str(i)
		return ans


class Solution:

	def largestNum(self, n, s):
		if 9 * n < s:
			return '-1'
		result = ''
		arr = [0 for i in range(n)]
		i = 0
		while s != 0 and i < n:
			if s >= 9:
				arr[i] = 9
				s -= 9
			else:
				arr[i] = s
				s = 0
				break
			i += 1
		res = ''
		for j in arr:
			res += str(j)
		return res


class Solution:

	def largestNum(self, n, s):
		if 9 * n < s:
			return -1
		ans = ''
		count = n
		while n > 0:
			if s - 9 > 0:
				ans += '9'
				s = s - 9
			else:
				ans += str(s)
				s = 0
			n = n - 1
		return ans


class Solution:

	def largestNum(self, n, s):
		l1 = [0] * n
		num = 9
		l = s
		for i in range(n):
			if num <= l:
				l1[i] = num
				l -= num
			else:
				l1[i] = l
				l -= l
		if sum(l1) != s:
			return -1
		ans = ''
		for i in l1:
			ans += str(i)
		return ans


class Solution:

	def largestNum(self, n, s):
		k = 0
		c = 0
		o = s
		if n * 9 < s:
			return -1
		else:
			while s:
				if s >= 9:
					k = k * 10 + 9
					s = s - 9
					c = c + 1
				else:
					k = k * 10 + s
					s = 0
					c = c + 1
		if o == 0:
			k = ''
		m = n - c
		if m == 0:
			return k
		else:
			k = str(k)
			k = list(k)
			for i in range(0, m):
				k.append('0')
			k = ''.join(k)
			return k


class Solution:

	def largestNum(self, n, s):
		t = ''
		for i in range(9, 0, -1):
			c = s // i
			t += str(i) * c
			s %= i
		if len(t) > n:
			return -1
		if len(t) < n:
			t += (n - len(t)) * '0'
		return t


class Solution:

	def largestNum(self, n, s):
		if n * 9 < s:
			return -1
		if n * 9 == s:
			return '9' * n
		a = s // 9
		if a == 0:
			return str(s) + '0' * (n - 1)
		return '9' * a + str(s % 9) + '0' * (n - a - 1)


class Solution:

	def largestNum(self, n, s):
		if s == 0:
			if n == 1:
				return 0
		if s > 9 * n:
			return -1
		res = [0] * n
		for i in range(n):
			if s >= 9:
				res[i] = '9'
				s -= 9
			else:
				res[i] = str(s)
				s = 0
		return ''.join(res)


class Solution:

	def largestNum(self, n, s):
		q = s // 9
		if q > n:
			return -1
		if q == n:
			if s % 9 != 0:
				return -1
			else:
				return '9' * n
		r = ''
		while s > 9:
			r += '9'
			s -= 9
			n -= 1
		r += str(s)
		n -= 1
		while n > 0:
			r += '0'
			n -= 1
		return r


class Solution:

	def largestNum(self, n, s):
		ans = [0] * n
		for i in range(n):
			v = min(9, s)
			ans[i] = v
			s -= v
		if s > 0:
			return '-1'
		return ''.join((str(v) for v in ans))


class Solution:

	def largestNum(self, n, s):
		num = s
		st = ''
		cnt = 0
		while n:
			if s >= 9:
				st += '9'
				s -= 9
				cnt += 9
			elif s == 0:
				st += '0'
			else:
				cnt += s
				st += str(s)
				s = 0
			n -= 1
		return st if cnt == num else -1


class Solution:

	def largestNum(self, D, S):
		if D * 9 < S:
			return -1
		if S == 0:
			return '0' * D
		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 largestNum(self, n, s):
		x = ''
		if n == 1 and s == 1:
			return 1
		if s == 0:
			for i in range(n):
				x += str(0)
			return x
		p = s
		ss = s
		i = 0
		v = ''
		for ii in range(n + 1):
			if p == 0:
				break
			elif i == ss:
				break
			else:
				if p - 9 >= 0:
					p -= 9
					i += 9
					v += str(9)
					continue
				if p - 8 >= 0:
					p -= 8
					i += 8
					v += str(8)
					continue
				if p - 7 >= 0:
					p -= 7
					i += 7
					v += str(7)
					continue
				if p - 6 >= 0:
					p -= 6
					i += 6
					v += str(6)
					continue
				if p - 5 >= 0:
					p -= 5
					i += 5
					v += str(5)
					continue
				if p - 4 >= 0:
					p -= 4
					i += 4
					v += str(4)
					continue
				if p - 3 >= 0:
					p -= 3
					i += 3
					v += str(3)
					continue
				if p - 2 >= 0:
					p -= 2
					i += 2
					v += str(2)
					continue
				if p - 1 >= 0:
					p -= 1
					i += 1
					v += str(1)
					continue
		vv = v
		ans = int(v)
		if i == ss and len(vv) <= n:
			if len(v) == n:
				return ans
			b = n - len(v)
			if b > 1:
				ans *= 10 ** b
				return ans
			return ans * 10
		return -1


class Solution:

	def largestNum(self, n, s):
		if s / n > 9:
			return -1
		if s == 0:
			return '0' * n
		ans = ''
		for i in range(n):
			if s == 0:
				ans += '0'
			elif s <= 9:
				ans += str(s)
				s = 0
			else:
				ans += '9'
				s -= 9
		return int(ans)


class Solution:

	def largestNum(self, n, s):
		ans = ''
		if s > 9 * n:
			return -1
		else:
			x = s // 9
			ans += '9' * x
			if s % 9 != 0:
				ans += str(s % 9)
			while len(ans) < n:
				ans += '0'
			return ans


class Solution:

	def largestNum(self, n, s):
		d = []
		if s > 9 * n:
			return '-1'
		else:
			for i in range(n):
				if s > 9:
					s -= 9
					d.append(9)
				else:
					d.append(s)
					s = 0
			str_list = list(map(str, d))
			res = ''.join(str_list)
			return res


class Solution:

	def largestNum(self, n, s):
		q = s // 9
		p = s % 9
		if q > n:
			return -1
		if p != 0:
			l = '9' * q + str(p) + '0' * (n - q - 1)
		else:
			l = '9' * q + '0' * (n - q)
		if len(l) == n:
			return l
		return -1


class Solution:

	def largestNum(self, n, s):
		dig = ''
		if n * 9 < s:
			return -1
		elif s == 0:
			return '0' * n
		while s >= 0:
			if s >= 9:
				s -= 9
				dig += '9'
			else:
				for i in range(8, 0, -1):
					if s - i >= 0:
						s -= i
						dig += str(i)
				if s == 0:
					break
				elif s - i < 0:
					dig += str(s)
					break
		if s < 0:
			return -1
		else:
			return int(dig + '0' * (n - len(dig)))


class Solution:

	def largestNum(self, n, s):
		if s > 9 * n:
			return '-1'
		res = ''
		for i in range(n):
			d = min(s, 9)
			res += str(d)
			s -= d
		return res


class Solution:

	def largestNum(self, n, s):
		if s == 0:
			return '0' * n
		a = s // 9
		b = s % 9
		if b != 0:
			ans = '9' * a + str(b)
		else:
			ans = '9' * a
		k = len(ans)
		if k <= n:
			ans = ans + (n - k) * '0'
			return ans
		else:
			return -1


class Solution:

	def largestNum(self, n, s):
		res = ''
		if n < len(str(s)):
			return -1
		if s > 9 * n:
			return -1
		if s <= 9:
			res += str(s)
			for i in range(n - 1):
				res += '0'
			return res
		else:
			while 1:
				res += '9'
				s = s - 9
				if s <= 9:
					break
			res += str(s)
			for j in range(n - len(res)):
				res += '0'
			return res
		return -1


class Solution:

	def largestNum(self, N, S):
		arr = [0] * N
		for i in range(len(arr)):
			if S > 9:
				arr[i] = 9
				S = S - 9
			else:
				arr[i] = S
				S = 0
		if S != 0:
			return -1
		s = ''.join((str(i) for i in arr))
		return s


class Solution:

	def largestNum(self, n, s):
		if s > 9 * n:
			return -1
		password = ''
		k = 9
		while n and k >= 0:
			if s - k >= 0:
				password += str(k)
				s -= k
				n -= 1
			else:
				k -= 1
		if n:
			password += str(0) * n
		return password


class Solution:

	def largestNum(self, n, s):
		str_final = ''
		sum = s
		for i in range(n):
			if sum >= 9 and n > 1:
				sum = sum - 9
				str_final = str_final + '9'
			elif sum < 9 and sum > -1:
				str_final = str_final + str(sum)
				sum = 0
		if len(str_final) == 0 or sum != 0:
			return '-1'
		return str_final


class Solution:

	def largestNum(self, n, s):
		res = ''
		while n and s >= 9:
			res += str(9)
			n -= 1
			s -= 9
		if n and s:
			res += str(s)
			s = 0
			n -= 1
			if n:
				res += '0' * n
			return res
		elif n and (not s):
			res += '0' * n
			return res
		elif not n and s:
			return -1
		else:
			return res


class Solution:

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


class Solution:

	def largestNum(self, n, s):
		if 9 * n < s:
			return -1
		if s == 0:
			return '0' * n
		if s <= 9:
			return s * 10 ** (n - 1)
		num = 9
		s -= 9
		n -= 1
		while s >= 9 and n > 0:
			num = num * 10 + 9
			n -= 1
			s -= 9
		if s < 9 and n > 0:
			num = num * 10 + s
			s -= s
			n -= 1
		while n > 0:
			num *= 10
			n -= 1
		return num


class Solution:

	def largestNum(self, n, s):
		num = ''
		if s == 0:
			return '0' * n
		for i in range(n):
			if s > 9:
				num += str(9)
				s -= 9
			else:
				num += str(s)
				s = 0
				break
		if len(num) < n:
			num = num + '0' * (n - len(num))
		if s > 0:
			return -1
		return int(num)


class Solution:

	def largestNum(self, n, s):
		s1 = ''
		if n * 9 >= s:
			for i in range(n):
				temp = s - i * 9
				if temp >= 9:
					s1 += '9'
				elif temp >= 0:
					s1 += str(temp)
				else:
					s1 += '0'
			return s1
		else:
			return -1


class Solution:

	def largestNum(self, n, s):
		n1 = n
		if s == 0:
			return '0' * n
		res = ''
		while s > 0 and n > 0:
			if s > 9:
				res += '9'
				s -= 9
				n -= 1
			else:
				res += str(s)
				n -= 1
				s = 0
		if s != 0:
			return '-1'
		res += (n1 - len(res)) * '0'
		return res


class Solution:

	def largestNum(self, n, s):
		a = ''
		i = 0
		while s > 0:
			if s >= 9:
				s -= 9
				a += '9'
			elif s >= 8:
				s = s - 8
				a += '8'
			elif s >= 7:
				s = s - 7
				a += '7'
			elif s >= 6:
				s = s - 6
				a += '6'
			elif s >= 5:
				s = s - 5
				a += '5'
			elif s >= 4:
				s = s - 4
				a += '4'
			elif s >= 3:
				s = s - 3
				a += '3'
			elif s >= 2:
				s = s - 2
				a += '2'
			elif s >= 1:
				s = s - 1
				a += '1'
			i += 1
			if i > n:
				break
		if len(a) > n:
			return -1
		b = n - len(a)
		for i in range(0, b):
			a += '0'
		return a


class Solution:

	def largestNum(self, n, s):
		e_dsum = s
		c_dsum = 0
		num = 0
		mult = 10 ** (n - 1)
		str1 = ''
		if e_dsum == 0:
			for i in range(0, n):
				str1 += '0'
		elif e_dsum > n * 9:
			num = -1
			str1 = str(num)
		elif e_dsum <= 9:
			num = e_dsum * mult
			str1 = str(num)
		else:
			while c_dsum < e_dsum:
				diff = e_dsum - c_dsum
				if diff < 9:
					num = num + diff * mult
					c_dsum = c_dsum + diff
				else:
					num = num + 9 * mult
					c_dsum = c_dsum + 9
				mult //= 10
			str1 = str(num)
		return str1


class Solution:

	def largestNum(self, n, s):
		ans = 0
		if s > 9 * n:
			return -1
		if s == 0:
			return ''.join(('0' for _ in range(n)))
		s1 = ''
		for i in range(n):
			if s >= 9:
				s1 = s1 + '9'
				s -= 9
			elif s < 9 and s > 0:
				s1 += str(s)
				s = 0
			else:
				s1 += '0'
		return s1


class Solution:

	def largestNum(self, n, s):
		m = ''
		while s > 0:
			if s >= 9:
				m += '9'
				s -= 9
			else:
				m += str(s)
				break
			if len(m) > n:
				break
		if len(m) > n:
			return -1
		else:
			r = n - len(m)
			m += '0' * r
		return m


class Solution:

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


class Solution:

	def largestNum(self, n, s):
		if s > n * 9:
			return '-1'
		elif s == 0:
			res = ''
			for i in range(n):
				res += '0'
			return res
		else:
			res = ''
			num = 0
			while num < n:
				if s != 0:
					if s >= 9:
						s = s - 9
						res += '9'
					else:
						s = str(s)
						res += s
						num += 1
						break
				else:
					break
				num += 1
			rem = n - num
			for i in range(rem):
				res += '0'
			return res


class Solution:

	def largestNum(self, n, s):
		res = ''
		if s > n * 9:
			return -1
		while s > 0:
			if s >= 9:
				res += '9'
				s -= 9
			else:
				res += str(s)
				break
		if len(res) < n:
			k = n - len(res)
			res += k * '0'
		return res


class Solution:

	def largestNum(self, n, s):
		Num = ''
		while s > 0 and n > 0:
			if s >= 9:
				Num += '9'
				s -= 9
				n -= 1
			elif s < 9:
				Num += str(s)
				n -= 1
				s = 0
		if s > 0:
			return -1
		while n > 0:
			Num += '0'
			n -= 1
		return Num


class Solution:

	def largestNum(self, n, s):
		if s > n * 9:
			return -1
		if s == n * 9:
			return '9' * n
		if s == 0:
			return '0' * n
		(quotient, remainder) = (s // 9, s % 9)
		(result, count) = ('', 1)
		for i in range(quotient):
			result += '9'
			count += 1
		result += str(remainder)
		for i in range(count, n):
			result += '0'
		return result


class Solution:

	def largestNum(self, n, s):
		if s > 9 * n:
			return -1
		result = ['9'] * (s // 9)
		if s % 9:
			result += [str(s % 9)]
		n -= len(result)
		result += ['0'] * n
		return ''.join(result)


class Solution:

	def largestNum(self, n, s):
		num = ''
		curr_sum = 0
		for i in range(n):
			if curr_sum + 9 < s:
				num = num + '9'
				curr_sum += 9
			elif curr_sum < s:
				num = num + str(s - curr_sum)
				curr_sum = s
			else:
				num = num + '0'
		if curr_sum < s:
			return -1
		return num


class Solution:

	def largestNum(self, n, s):
		if n == 0:
			return -1
		if s == 0:
			return '0' * n
		if s > n * 9:
			return -1
		num = 0
		for _ in range(n):
			digit = min(9, s)
			num = num * 10 + digit
			s -= digit
		return str(num)


class Solution:

	def largestNum(self, n, s):
		r = ''
		for i in range(0, n):
			if s >= 9:
				r += '9'
				s = s - 9
			else:
				r += str(s)
				s = 0
				break
		if s != 0:
			return -1
		return r + '0' * (n - i - 1)