#1. On a phone keypad, many of the numbers have letters associated with them. Fo

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

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.