> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/winning-lottery.md).

# Winning Lottery

Harshit knows by his resources that this time the winning lottery number is the smallest number whose sum of the digits is S and the number of digits is D. You have to help Harshit and print the winning lottery number.

**Input Format**

```
The Input line contains two space-separated integers: S,D
```

**Output Format**

```
The output contains a single integer denoting the winning lottery number
```

**Constraints**

```
1 <= D <= 1000
1 <= S <= 9*D
Time Limit: 1 second
```

**Sample Input1:**

```
9 2
```

**Sample Output1:**

```
18
```

**Explanation**

```
There are many other possible numbers like 45, 54, 90, etc with the sum of digits as 9 and number of digits as 2. The smallest of them is 18.
```

```java
class Main {
    public static String findSmallest(int sum, int digits) {
        // We want the smallest number, so we can just
        // start giving biggest digits possible to last positions(LSP)
        char[] str = new char[digits];
        for (int i = digits - 1; i >= 0; i--) {
            int digit = 9;
            // Reserving 1 for the first digit
            if (digit + 1 > sum)
                if (i == 0)
                    digit = sum;
                else
                    digit = sum - 1;
            str[i] = (char) (digit + '0');
            sum -= digit;
        }
        return new String(str);
    }
}
```