TopCoder Statistics - Problem Statement

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"
1

Returns: "111111117"
2

Returns: "111111171"
3

Returns: "111111711"
4

Returns: "111117111"
5

Returns: "111171111"
6

Returns: "111711111"
7

Returns: "117111111"
8

Returns: "171111111"
9

Returns: "711111111"
10

Returns: "111111114"
11

Returns: "111111141"
12

Returns: "111111177"
13

Returns: "111111411"
14

Returns: "111111717"
15

Returns: "111111771"
16

Returns: "111114111"
17

Returns: "111117117"
18

Returns: "111117171"
19

Returns: "111117711"
20

Returns: "111141111"
377792061

Returns: "357469281"
7

Returns: "117111111"
999999992

Returns: "888888988"
594466527

Returns: "802170964"
27638

Returns: "111211447"
999972361

Returns: "980888308"
276411094

Returns: "106529515"
116202

Returns: "371441171"
999883797

Returns: "988666080"
421352848

Returns: "855247759"
567183

Returns: "351171127"
999432816

Returns: "896888284"
853713590

Returns: "238248400"
8579

Returns: "771111271"
999991420

Returns: "888880895"
110011152

Returns: "146772539"
999999998

Returns: "988888888"
850666256

Returns: "120999839"
33366

Returns: "117114241"
999966633

Returns: "898883008"
985054821

Returns: "568588876"
109464962

Returns: "141296795"
890535037

Returns: "909494849"
609421745

Returns: "963944354"
11961

Returns: "113711714"
999988038

Returns: "880898866"
255273378

Returns: "750914246"
112601

Returns: "271477117"
999887398

Returns: "988893869"
999999999

Returns: "888888888"

Statistics

Problem Statement for "MatchstickNumbers"

Problem Statement

Definition

Constraints

Examples