We are all familiar with alpha numeric keypad that was used for messaging in earlier days. Given sequence of numbers 2-9 (both inclusive), find out the number of distinct alphabets that can be formed.
The rules of interpreting keypad strokes are as follows
1) Let’'s understand with example. 25 can mean AJ but it can also mean pressing button 5 two times. In that case it becomes K. See Examples section for better understanding.
2) Maximum number of distinct alphabets that can be formed cannot exceed 26
3) Alphanumeric keyboard used is as follows
· key 2 has letters "A B C"
· key 3 has letters "D E F"
· key 4 has letters "G H I"
· key 5 has letters "J K L"
· key 6 has letters "M N O"
· key 7 has letters "P Q R S"
· key 8 has letters "T U V"
· key 9 has letters "W X Y Z"
4) Input does not contain either 1 or 0 because no keypad buttons are associated with these numbers.
Constraints
1 <= Length of Input Literals <= 40
Input Format
Single Line contains a number with literals [2-9]
Output
Number of distinct alphabets after factoring all possible interpretations of the input
Explanation
Example 1
Input
253
Output
5
Explanation
It can be interpreted as AJD, KD , AE, thus distinct alphabets formed- A , J , D ,K , E = 5 distinct alphabets.
Example 2
Input
294
Output
5
Answers
#include <iostream>
#include<malloc.h>
#include<string.h>
using namespace std;
int common(int a[],int b[],int count)//Finds no. of common numbers in input
{
int k=0,l=0;
for(int i=0;i<count;i++)
{
for(int j=0;j<i;j++)
{
if(a[j]==a[i])
{
int z=0;
for(int m=0;m<l;m++)
{
if(a[m]==b[l])
z++;
}
if(z==0)
{
*(b+l)=a[i];
l++;
}
k++;
break;
}
}
}
return k;
}
int main()
{
char buf[40];
int b[26];
int c[26];
int k=0;
int *array;
int*l;
cin>>buf;
array = (int*)malloc(strlen(buf) * sizeof(int)); //Allocate Memory
int i=0,count=0;
do{
array[i] = buf[i]-'0';
count++;
}while(buf[++i]);
int x=common(array,b,count);
c[0]=b[0];
int m=1;
for(i=1;i<x;i++)
{
int s=0;
for(int j=0;j<i;j++)
{
if(c[j]==b[i])
{
s++;
break;
}
}
if(s==0)
{
c[m]=b[i];
m++;
}
}
int ghost[26];
int barbara[26];
int cot=0;
for(int i=0;i<(m-1);i++)
{
int kind=0;
for(int j=0;j<count;j++)
{
if(array[j]==c[i])
{
if(array[j-1]==7|| array[j-1]==9)
ghost[kind]=(array[j-1])%4;
else
ghost[kind]=(array[j-1])%3;
kind++;
}
}
cot+=common(ghost,barbara,kind);
}
cout<<(2*count-1-((m-1)+cot));
}