IntrospectiveNumbers
SRM 817 · 2021-10-21 · by misof
Problem Statement
An introspective number is a positive integer such that each digit of the number tells you the number of occurrences of that digit in that number.
For example, the number 2144424 is introspective because it has one 1, two 2s, and four 4s.
Clearly there are only finitely many introspective numbers.
Suppose we sorted all of them.
Given the
Notes
- The total number of introspective numbers is greater than 10^18, so for any input that matches the constraints given below the return value is defined.
Constraints
- index will be between 0 and 10^18, inclusive.
0 Returns: "1"
The smallest introspective number (i.e., the one at index 0) is clearly the number 1.
5 Returns: "333"
The only two-digit introspective number is 22. The three-digit ones are 122, 212, 221, and 333.
128 Returns: "2144424"
The correct answer for this index is the number mentioned in the statement.
266960 Returns: "999299999912"
1 Returns: "22"
Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IntrospectiveNumbers with a public method string nth(long long index) · 64 test cases · 2 s / 256 MB per case