MatchstickNumbers
2022 HF Final · 2022-03-16 · by misof
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
Constraints
- N will be between 0 and 10^9 - 1, inclusive.
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.
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MatchstickNumbers with a public method string index(int N) · 56 test cases · 2 s / 256 MB per case