LoopsyDoopsy | Topcoder Archive

Problem Statement

The number of loops in a digit is the number of closed regions you produce when you write the digit on paper. For example, "1" has no loops, "9" has one loop, and "8" has two. (As the number of loops depends on the font you use, the exact numbers of loops we are using in this problem are given in the Notes.)

By extension, the number of loops in any nonnegative integer is the total number of loops in its individual digits. For example, "2461" has two loops and "1890" has four.

You are given the int loops. Find the smallest nonnegative integer with exactly loops loops and return it as a String. Note that the returned String cannot have unnecessary leading zeros.

Definition

Class:: LoopsyDoopsy
Method:: getSmallestNumber
Parameters:: int
Returns:: String
Method signature:: String getSmallestNumber(int loops)
(be sure your method is public)

Notes

The digits 0 through 9 have 1, 0, 0, 0, 1, 0, 1, 0, 2, and 1 loops, respectively.

Constraints

loops will be between 1 and 2,500, inclusive.

Examples

```
1
```
```
Returns: "0"
```
0, 4, 6, 9, 10, 24 are some of the non-negative integers with exactly 1 loop.
```
2
```
```
Returns: "8"
```
8, 49, 66, 100 are some of the non-negative integers with exactly 2 loops.
```
40
```
```
Returns: "88888888888888888888"
```
Watch out for integer overflow.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.