MatchstickNumbers | Topcoder Archive

Problem Statement

Below is one specific way how to make digits out of matchsticks. Each '-' and each '|' represents one matchstick.

   +  +-+  +-+  + +  +-+
   |    |    |  | |  |
   +  +-+  +-+  +-+  +-+
   |  |      |    |    |
   +  +-+  +-+    +  +-+

 +-+  +-+  +-+  +-+  +-+
 |      |  | |  | |  | |
 +-+    +  +-+  +-+  + +
 | |    |  | |    |  | |
 +-+    +  +-+  +-+  +-+

We have taken all 10^9 nine-digit strings: from 000000000 to 999999999.

We have ordered them according to the number of matchsticks needed to build each of them (smaller to larger). Ties were broken using their numerical value (again, smaller to larger).

Given a 0-based index N into the sorted sequence, return a 9-digit String that is located at that index.

Definition

Class:: MatchstickNumbers
Method:: index
Parameters:: int
Returns:: String
Method signature:: String index(int N)
(be sure your method is public)

Constraints

N will be between 0 and 10^9 - 1, inclusive.

Examples

```
0
```
```
Returns: "111111111"
```
The only number that can be built using only 18 matchsticks is "111111111".
```
4
```
```
Returns: "111117111"
```
The next few numbers are the numbers that can be built using 19 matchsticks: at index 1 we have "111111117", at index 2 "111111171", at index 3 "111111711", and at index 4 we have "111117111".
```
10
```
```
Returns: "111111114"
```
At index 10 is the smallest 9-digit number that requires 20 matchsticks.
```
12
```
```
Returns: "111111177"
```
After "111111141" at index 11 we have "111111177" at index 12.
```
999999993
```
```
Returns: "888889888"
```
One of the numbers that require a very large number of matchsticks.
```
123456789
```
```
Returns: "418035721"
```

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.