In how many ways can the 7 letters m n o

In numeric keyboards, texts and numbers are placed on the same key. For example 2 has “ABC” if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. below is picture of such keypad.

keypad //d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png

Given a keypad as shown in diagram, and a n digit number, list all words which are possible by pressing these numbers.

For example if input number is 234, possible words which can be formed are (Alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

Let’s do some calculations first. How many words are possible with seven digits with each digit representing n letters? For first digit we have at most four choices, and for each choice for first letter, we have at most four choices for second digit and so on. So it’s simple maths it will be O(4^n). Since keys 0 and 1 don’t have any corresponding alphabet and many characters have 3 characters, 4^n would be the upper bound of number of words and not the minimum words.

Now let’s do some examples.

For number above 234. Do you see any pattern? Yes, we notice that the last character always either G,H or I and whenever it resets its value from I to G, the digit at the left of it gets changed. Similarly whenever the second last alphabet resets its value, the third last alphabet gets changes and so on. First character resets only once when we have generated all words. This can be looked from other end also. That is to say whenever character at position i changes, character at position i+1 goes through all possible characters and it creates ripple effect till we reach at end. Since 0 and 1 don’t have any characters associated with them. we should break as there will no iteration for these digits.

Let’s take the second approach as it will be easy to implement it using recursion. We go till the end and come back one by one. Perfect condition for recursion. let’s search for base case. When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.

Following is C implementation of recursive approach to print all possible word corresponding to a n digit input number. Note that input number is represented as an array to simplify the code.

#include <stdio.h> #include <string.h> // hashTable[i] stores all characters that correspond to digit i in phone const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // A recursive function to print all possible words that can be obtained // by input number[] of size n. The output words are one by one stored // in output[] void printWordsUtil(int number[], int curr_digit, char output[], int n) { // Base case, if current output word is prepared int i; if (curr_digit == n) { printf("%s ", output); return ; } // Try all 3 possible characters for current digir in number[] // and recur for remaining digits for (i=0; i<strlen(hashTable[number[curr_digit]]); i++) { output[curr_digit] = hashTable[number[curr_digit]][i]; printWordsUtil(number, curr_digit+1, output, n); if (number[curr_digit] == 0 || number[curr_digit] == 1) return; } } // A wrapper over printWordsUtil(). It creates an output array and // calls printWordsUtil() void printWords(int number[], int n) { char result[n+1]; result[n] ='\0'; printWordsUtil(number, 0, result, n); } //Driver program int main(void) { int number[] = {2, 3, 4}; int n = sizeof(number)/sizeof(number[0]); printWords(number, n); return 0; }

Output:

adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

Time Complexity:

Time complexity of above code is O(4^n) where n is number of digits in input number.

References:

//www.flipkart.com/programming-interviews-exposed-secrets-landing-your-next-job-3rd/p/itmdxghumef3sdjn?pid=9788126539116&affid=sandeepgfg

Page 2

During a job interview I received this question regarding creating an array of and printing out all possible letter combinations of a phone number. During the interview I received a whisper from my interviewer about recursion and how it can't be done using loops. Very unnatural for me to receive input from another programmer, I trusted his advice instead of my own tuition and proceeded to write up a sloppy recursion mess. It didn't go so well. Before receiving input, as I had never received this problem before, my brain was calculating up the underlying replicable mathematical formula. Whispers under my breath, "can't just multiply by three, some of them are four" as my mind started racing against a short clock thinking about one answer while beginning to write another. It was not until the end of the week I received my call to let me know the sad news. It was later that night I decided to see if it really is a recursion problem. Turns out for me it isn't.

My solution below is coded in PHP, is non-recursive, works with any length of input and I've even included some comments to help describe what my variables mean. Its my official and unchanging final answer to this question. I hope this helps somebody else in the future, please feel free to translate this into other languages.

Me method involves calculating the total number of combinations and creating a buffer large enough to hold every byte. The length of my buffer is the same length you would expect to receive from a working recursive algorithm. I make an array that contains the groups of letters that represent each number. My method primarily works because your combo total will always be divisible by the number of letters in the current group. If you can imagine in your head a vertical list of the output of this algorithm, or see the list vertically as opposed to a horizontally written list of the combinations, my algorithm will begin to make sense. This algorithm allows us to loop through each byte vertically from top to bottom starting from the left instead of horizontally left to right, and populate each byte individually without requiring recursion. I use the buffer as though its a byte array to save time and energy.

NON-RECURSIVE, ITERATIVE PHP

<?php // Display all possible combinations of letters for each number. $input = '23456789'; // ==================== if(!isset($input[0])) die('Nothing to see here!'); $phone_letters = array( 2 => array('a', 'b', 'c'), 3 => array('d', 'e', 'f'), 4 => array('g', 'h', 'i'), 5 => array('j', 'k', 'l'), 6 => array('m', 'n', 'o'), 7 => array('p', 'q', 'r', 's'), 8 => array('t', 'u', 'v'), 9 => array('w', 'x', 'y', 'z') ); $groups = array(); $combos_total = 1; $l = strlen($input); for($i = 0; $i < $l; ++$i) { $groups[] = $phone_letters[$input[$i]]; $combos_total *= count($phone_letters[$input[$i]]); } $count = $combos_total / count($groups[0]); $combos = array_fill(0, $combos_total, str_repeat(chr(0), strlen($input))); for( $group = 0, // Index for the current group of letters. $groups_count = count($groups), // Total number of letter groups. $letters = count($groups[0]), // Total number of letters in the current group. $width = $combos_total, // Number of bytes to repeat the current letter. $repeat = 1; // Total number of times the group will repeat. ; ) { for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r) for($l = 0; $l < $letters; ++$l) for($w = 0; $w < $width; ++$w) $combos[$byte++][$group] = $groups[$group][$l]; if(++$group < $groups_count) { $repeat *= $letters; $letters = count($groups[$group]); } else break; } // ==================== if(is_array($combos)) { print_r($combos); echo 'Total combos:', count($combos), "\n"; } else echo 'No combos.', "\n"; echo 'Expected combos: ', $combos_total, "\n";

NON-RECURSIVE, NON-ITERATIVE, NO-BUFFER, THREAD FRIENDLY, MATH ONLY + NON-RECURSIVE, ITERATIVE PHP OBJECT USING MULTI-BASE BIG ENDIAN

While I was working on the new house the other day, I had a realisation that I could use the mathematics from my first function coupled with my knowledge of base to treat all possible letter combinations of my input as a multi-dimensional number.

My object provides the functions necessary to store a prefered combination into a database, convert letters and numbers if it were required, pick out a combination from anywhere in the combination space using a prefered combination or byte and it all plays very well with multi-threading.

That being said, using my object I can provide a second answer that uses base, no buffer, no iterations and most importantly no recursion.

<?php class phone { public static $letters = array( 2 => array('a', 'b', 'c'), 3 => array('d', 'e', 'f'), 4 => array('g', 'h', 'i'), 5 => array('j', 'k', 'l'), 6 => array('m', 'n', 'o'), 7 => array('p', 'q', 'r', 's'), 8 => array('t', 'u', 'v'), 9 => array('w', 'x', 'y', 'z') ); // Convert a letter into its respective number. public static function letter_number($letter) { if(!isset($letter[0]) || isset($letter[1])) return false; for($i = 2; $i < 10; ++$i) if(in_array($letter, phone::$letters[$i], true)) return $i; return false; } // Convert letters into their respective numbers. public static function letters_numbers($letters) { if(!isset($letters[0])) return false; $length = strlen($letters); $numbers = str_repeat(chr(0), $length); for($i = 0; $i < $length; ++$i) { for($j = 2; $j < 10; ++$j) { if(in_array($letters[$i], phone::$letters[$j], true)) { $numbers[$i] = $j; break; } } } return $numbers; } // Calculate the maximum number of combinations that could occur within a particular input size. public static function combination_size($groups) { return $groups <= 0 ? false : pow(4, $groups); } // Calculate the minimum bytes reqired to store a group using the current input. public static function combination_bytes($groups) { if($groups <= 0) return false; $size = $groups * 4; $bytes = 0; while($groups !== 0) { $groups >> 8; ++$bytes; } return $bytes; } public $input = ''; public $input_len = 0; public $combinations_total = 0; public $combinations_length = 0; private $iterations = array(); private $branches = array(); function __construct($number) { if(!isset($number[0])) return false; $this->input = $number; $input_len = strlen($number); $combinations_total = 1; for($i = 0; $i < $input_len; ++$i) { $combinations_total *= count(phone::$letters[$number[$i]]); } $this->input_len = $input_len; $this->combinations_total = $combinations_total; $this->combinations_length = $combinations_total * $input_len; for($i = 0; $i < $input_len; ++$i) { $this->branches[] = $this->combination_branches($i); $this->iterations[] = $this->combination_iteration($i); } } // Calculate a particular combination in the combination space and return the details of that combination. public function combination($combination) { $position = $combination * $this->input_len; if($position < 0 || $position >= $this->combinations_length) return false; $group = $position % $this->input_len; $first = $position - $group; $last = $first + $this->input_len - 1; $combination = floor(($last + 1) / $this->input_len) - 1; $bytes = str_repeat(chr(0), $this->input_len); for($i = 0; $i < $this->input_len; ++$i) $bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])]; return array( 'combination' => $combination, 'branches' => $this->branches[$group], 'iterations' => $this->iterations[$group], 'first' => $first, 'last' => $last, 'bytes' => $bytes ); } // Calculate a particular byte in the combination space and return the details of that byte. public function combination_position($position) { if($position < 0 || $position >= $this->combinations_length) return false; $group = $position % $this->input_len; $group_count = count(phone::$letters[$this->input[$group]]); $first = $position - $group; $last = $first + $this->input_len - 1; $combination = floor(($last + 1) / $this->input_len) - 1; $index = ($combination / $this->branches[$group]) % $group_count; $bytes = str_repeat(chr(0), $this->input_len); for($i = 0; $i < $this->input_len; ++$i) $bytes[$i] = phone::$letters[$this->input[$i]][($combination / $this->branches[$i]) % count(phone::$letters[$this->input[$i]])]; return array( 'position' => $position, 'combination' => $combination - 1, 'group' => $group, 'group_count' => $group_count, 'group_index' => $index, 'number' => $this->input[$group], 'branches' => $this->branches[$group], 'iterations' => $this->iterations[$group], 'first' => $first, 'last' => $last, 'byte' => phone::$letters[$this->input[$group]][$index], 'bytes' => $bytes ); } // Convert letters into a combination number using Multi-Base Big Endian. public function combination_letters($letters) { if(!isset($letters[$this->input_len - 1]) || isset($letters[$this->input_len])) return false; $combination = 0; for($byte = 0; $byte < $this->input_len; ++$byte) { $base = count(phone::$letters[$this->input[$byte]]); $found = false; for($value = 0; $value < $base; ++$value) { if($letters[$byte] === phone::$letters[$this->input[$byte]][$value]) { $combination += $value * $this->branches[$byte]; $found = true; break; } } if($found === false) return false; } return $combination; } // Calculate the number of branches after a particular group. public function combination_branches($group) { if($group >= 0 && ++$group < $this->input_len) { $branches = 1; for($i = $group; $i < $this->input_len; ++$i) $branches *= count(phone::$letters[$this->input[$i]]); return $branches === 1 ? 1 : $branches; } elseif($group === $this->input_len) return 1; else return false; } // Calculate the number of iterations before a particular group. public function combination_iteration($group) { if($group > 0 && $group < $this->input_len) { $iterations = 1; for($i = $group - 1; $i >= 0; --$i) $iterations *= count(phone::$letters[$this->input[$i]]); return $iterations; } elseif($group === 0) return 1; else return false; } // Iterations, Outputs array of all combinations using a buffer. public function combinations() { $count = $this->combinations_total / count(phone::$letters[$this->input[0]]); $combinations = array_fill(0, $this->combinations_total, str_repeat(chr(0), $this->input_len)); for( $group = 0, // Index for the current group of letters. $groups_count = $this->input_len, // Total number of letter groups. $letters = count(phone::$letters[$this->input[0]]), // Total number of letters in the current group. $width = $this->combinations_total, // Number of bytes to repeat the current letter. $repeat = 1; // Total number of times the group will repeat. ; ) { for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r) for($l = 0; $l < $letters; ++$l) for($w = 0; $w < $width; ++$w) $combinations[$byte++][$group] = phone::$letters[$this->input[$group]][$l]; if(++$group < $groups_count) { $repeat *= $letters; $letters = count(phone::$letters[$this->input[$group]]); } else break; } return $combinations; } } // ==================== $phone = new phone('23456789'); print_r($phone); //print_r($phone->combinations()); for($i = 0; $i < $phone->combinations_total; ++$i) { echo $i, ': ', $phone->combination($i)['bytes'], "\n"; }