Problem of the Week

Problem 11 Solution

Congratulations to Joshua Sargent from Soham Village College, Keo Osman from Simon Balle School, Felix Reiter from Bottisham Village College and Yat Sum from Cambourne Village College for successfully solving this problem!
Below is the solution.

Given a position $n = 3{,}692{,}394{,}004{,}591{,}304{,}012{,}115{,}011{,}759{,}838{,}130{,}024$ in a lexicographical ordering (alphabetical ordering but for strings of multiple characters) of all possible 27-character passwords composed of uppercase letters (from A to Z), we want to find the password corresponding to this position by converting from base-10 to base-26.

To convert a base-10 number to a base-26 representation, we interpret each letter in the password as a “digit” in a base-26 numbering system, where:
– A corresponds to 0,
– B corresponds to 1,
$\ldots$
– Z corresponds to 25.

Here is the idea for the algorithm:

1. Subtract 1 from $n$ to account for zero-based indexing.
2. For each of the 27 positions in the password, determine the current “digit” by calculating the remainder of $n$ divided by 26.
3. Convert this remainder to the corresponding character using the mapping defined above.
4. Update $n$ by performing an integer division by 26 to move to the next position.
5. Since characters are computed from the least significant to the most significant position, reverse the resulting list of characters to obtain the final password.