Task is to use a standard substitution cipher where a = 1...z = 26. Find the English word that produces a value closes to 1 million when you multiply the letters together.

Second part of the question was to find English word would give the biggest value.

Answer

I was asked this question about three years ago, and during the interview the best I could come out with was word “hotdog” value 1,008,000. My initial approach was to find short word and grow it to 1M by adding suffixes such as dog->dogs->doggy->… Then playing with couple short word, I figure out that combining them would give very good result, i.e hotdog.

After the interview I decided to write simple brute force calculation against English dictionary to get exact answers. Here is the dictionary I used. The code is very primitive and simply iterates all words in dictionary and calls Cipher function:


private static long Cipher(string line)
{
if (string.IsNullOrEmpty(line)) return 0;

long result= 1;
line = line.ToUpper();
int A = (int)'A';
foreach (char letter in line)
{
result*= 1+(int)letter-A;
}
return sum;
}}


The results are:

The biggest cipher from my dictionary would give word “untrusting”

And the word “typey” is actually equals to exact 1,000,000 following by “curing” and “uncini” 1,000,188

typey 1000000
curing 1000188
uncini 1000188
comers 1000350
cozies 1000350
moors 1000350
remise 1000350
rooms 1000350
seamier 1000350
seriema 1000350
banquet 999600
banksias 1000692
savins 1000692
snarks 1000692
sulks 1000692







Answers and Comments