#1. On a phone keypad, many of the numbers have letters associated with them. Fo
ID: 3805896 • Letter: #
Question
#1. On a phone keypad, many of the numbers have letters associated with them. For instance, the letters A, B, and C are associated with the number 2. Write a C/C++ program that accepts a number as input and prints all of the possible letter combinations associated with that number. For example, if the input is n=23, the possible letter combinations are AD, AE, AF, BD, BE, BF, CD, CE, and CF.
#2. Measure the execution time of your program from Problem 1 as you vary the value of n. Remove the print statements before measuring the execution time. Plot this execution time as a function of n. You should measure the execution time for each value of n at least five times. Choose values of n such that your execution time ranges from less than a second to more than 30 seconds. What relationship do you see between n and the execution time?
Explanation / Answer
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 printCombnUtil(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];
printCombnUtil(number, curr_digit+1, output, n);
if (number[curr_digit] == 0 || number[curr_digit] == 1)
return;
}
}
// A wrapper over printCombnUtil(). It creates an output array and
// calls printCombnUtil()
void printCombn(int number[], int n)
{
char result[n+1];
result[n] ='';
printCombnUtil(number, 0, result, n);
}
//Driver program
int main(void)
{
// we are selecting the number 2 and 3.
int number[] = {2, 3};
int n = sizeof(number)/sizeof(number[0]);
printCombn(number, n);
return 0;
}
OUTPUT:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.