Connection Status:
Competition Arena > WordNumber

WordNumber

SRM 267 · 2005-10-05 · by dgoodman

SRM 267 · 2005-10-05 · by dgoodman · Math
Class Name: WordNumber
Return Type: String
Method Name: theWord
Arg Types: (int, int)
Problem Statement

Problem Statement

It is possible to number all the words that could be formed from a specified alphabet. One way to do it is to put the words in order based on length, with words of common length ordered alphabetically. Using this scheme, if we use the alphabet consisting of just the 3 letters 'a', 'b', and 'c' then the words are numbered: 
   1:a 2:b 3:c 4:aa 5:ab 6:ac 7:ba 8:bb   etc.
There are an infinite number of possible words, but each has its own positive number.

We want to be able to find the word that corresponds to any given number. Create a class WordNumber that contains a method theWord that is given alpha, the number of letters in the alphabet, and n, the number of a word. It returns the String that is the word corresponding to n.

The alphabet to be used is the first alpha letters of the normal lowercase alphabet, with their usual alphabetical ordering.

Constraints

  • alpha will be between 2 and 26, inclusive.
  • n will be between 1 and 2,000,000,000, inclusive.
Examples
0)
3
5
Returns: "ab"

See the table above.

1)
3
13
Returns: "aaa"

Extending the table above, we find that word 12 is "cc" so the next word, word 13, must be the first 3 letter word.

2)
26
2000000000
Returns: "flhomvx"
3)
15
1
Returns: "a"
4)
26
456
Returns: "qn"

Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WordNumber with a public method string theWord(int alpha, int n) · 62 test cases · 2 s / 256 MB per case

Submitting as anonymous