TelephoneNumbers
SRM 388 · 2008-01-15 · by bmerry
Problem Statement
Your company has received the contract to implement the new telephone system on the moon, where all telephone numbers will have 7 hexadecimal digits (see notes). The distance between two telephone numbers is the number of corresponding digits that differ. For example, the distance between 1b100fa and 11b0ffa is 3, because the 2nd, 3rd, and 5th digits (counting from the left) are different. In order to avoid wrong numbers, every pair of telephone numbers will have a distance of at least separation between them. Your policy for allocating telephone numbers is simple: each time a new number is required, the smallest possible number is assigned such that these conditions are preserved.
Your company is going to award a special prize to the person who is assigned the kth telephone number (k is 1-based). Return this number as a string of exactly 7 hexadecimal digits: '0' - '9' and lowercase 'a' - 'f'. The constraints guarantee that k is small enough for the prize to be awarded before it becomes impossible to allocate new numbers.
Notes
- Hexadecimal is base 16 (compared to "normal" numbers, which are base 10). The lowercase letters 'a' - 'f' are used to represent the digits with values 10 - 15. For example, the hexadecimal number 'af' is the same as the decimal number 10 * 16 + 15 = 175.
Constraints
- separation will be between 1 and 3, inclusive.
- k will be between 1 and 300,000, inclusive.
1 5 Returns: "0000004"
The first five phone numbers are simply 0000000, 0000001, 0000002, 0000003 and 0000004.
2 17 Returns: "0000101"
The first sixteen phone numbers are 00000?? for ? = 0, 1, ..., f.
3 33 Returns: "0002023"
1 1 Returns: "0000000"
1 2 Returns: "0000001"
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TelephoneNumbers with a public method string kthNumber(int separation, int k) · 65 test cases · 2 s / 256 MB per case