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.
Definition
- Class:
- TelephoneNumbers
- Method:
- kthNumber
- Parameters:
- int, int
- Returns:
- String
- Method signature:
- String kthNumber(int separation, int k)
- (be sure your method is public)
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.
Examples
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"
1
15
Returns: "000000e"
1
16
Returns: "000000f"
1
255
Returns: "00000fe"
1
256
Returns: "00000ff"
1
257
Returns: "0000100"
1
4095
Returns: "0000ffe"
1
4096
Returns: "0000fff"
1
4097
Returns: "0001000"
1
5012
Returns: "0001393"
1
61440
Returns: "000efff"
1
65244
Returns: "000fedb"
1
65535
Returns: "000fffe"
1
65536
Returns: "000ffff"
1
65537
Returns: "0010000"
1
300000
Returns: "00493df"
1
299999
Returns: "00493de"
2
1
Returns: "0000000"
2
2
Returns: "0000011"
2
3
Returns: "0000022"
2
15
Returns: "00000ee"
2
16
Returns: "00000ff"
2
17
Returns: "0000101"
2
18
Returns: "0000110"
2
40
Returns: "0000275"
2
41
Returns: "000028a"
2
49
Returns: "0000303"
2
65535
Returns: "00fffe1"
2
65536
Returns: "00ffff0"
2
100000
Returns: "01869f9"
2
200000
Returns: "030d3f2"
2
127715
Returns: "01f2e20"
2
209716
Returns: "0333333"
2
300000
Returns: "0493dfc"
3
1
Returns: "0000000"
3
2
Returns: "0000111"
3
3
Returns: "0000222"
3
15
Returns: "0000eee"
3
16
Returns: "0000fff"
3
17
Returns: "0001012"
3
18
Returns: "0001103"
3
40
Returns: "0002754"
3
41
Returns: "00028ab"
3
49
Returns: "0003031"
3
65535
Returns: "0fffe10"
3
65536
Returns: "0ffff01"
3
100000
Returns: "1869f92"
3
200000
Returns: "30d3f2a"
3
127715
Returns: "1f2e200"
3
209716
Returns: "3333333"
3
300000
Returns: "493dfc6"
3
299843
Returns: "4934285"
3
291457
Returns: "4728095"
3
276301
Returns: "4374c84"
3
42342
Returns: "0a565c2"
3
123456
Returns: "1e23f1f"
3
298777
Returns: "48f18a9"
3
291777
Returns: "473c0ce"
3
299998
Returns: "493dde4"
3
123123
Returns: "1e0f227"
3
298765
Returns: "48f0cff"