Problem: Largest number with given sum

A boy 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 possible with given sum S. As he is busy doing his homework, help him retrieving his password.

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains two space separated integers N and S, where N is the number of digits in password and S is the sum of all the digits of the password.

Output:
Corresponding to each test case, in a new line, print the largest integer if possible , else print -1.

Constraints:
1<= T <= 100
1<= N <= 10000
0<= S <= 100000000

Example:

Input:

3
5 12
3 29
3 26

Output:
93000
-1
998

Explanation :

In first test case, sum of elements is 12. Largest possible 5 digit number is 93000.
In second test case, there is no such three digit number whose sum is 29.

Python 2.7

t = input()
for _ in range(t):
    n, m = [int(x) for x in raw_input().split()]
    #n digits number will have max sum of its digit = n*9
    if 9*n &lt; m: 
        print -1
    else:
        s = ''
        if m &lt; 9:
            s += str(m)
        else:
            s += str(9)
            m -= 9
            while m &gt; 0:
                if m &gt;= 9:
                    s += str(9)
                else:
                    s += str(m)
                m -= 9
        s += ('0'*(n-len(s)))
        print s
Advertisements