C++ program to count possible decoding of a given digit sequence

Counting possible decoding of a given digit sequence in C++

Here we will discuss how to count all the possible decoding of a given digit sequence in C++. Before counting the number of decodings first let’s see how the numbers are assumed to be coded.

1 = A, 2 = B, 3 = C, . . . . , 26 = Z.
The decoding programs are the most possible questions asked and are largely practiced in C ++ programming. The program counts the number of possible decodings of the entered digit by the user of the given sequence.
For example, if the digit sequence is “12” then there are two possible decodings for this – One of them is ‘AB’ when we decode 1 as ‘A’ and 2 as ‘B’. Now we can also decode this digit sequence “12” as ‘L’ when we decode digits 1 and 2 taken together as an integer 12.

Now let’s take another example for reference,

Sequence = 131

  • Possible decoding (1, 3, 1,)    = ACA
  • Possible decoding (13, 1)   = MA
    So, the total possible decodings of sequence 131 is 2.
Possible decoding in C++

Working:-

Let’s see how the code works:

  • User gives an input(sequence of digits).
  • Input is stored in a char type array named digit.
  • Length of digit is found and stored in an int type variable say n.
  • A function is countDecoding() is called with digit and n as parameters.
  • An int type array is initialised named decodings[ ](to find the number of decodings).
  • A loop is started to count the decodings
  • Elements of digit are converted to int type.
  • They are checked for being in the range(1-26) and based on that changes are made to the decodings[ ]  array.
  • Number of decodings is returned.
  • Output is printed.
Possible decoding of a digit sequence in C++
Competitive Coding Techniques

C++ Code:-

//Count possible decodings of a given digit sequence
#include<iostream>
#include<string.h>
using namespace std;
//function to count the number of decodings
int countDecoding(char *digit, int n)
{
	int decodings[n+1];
	decodings[0]=1;
	decodings[1]=1;
	//counting decodings
	for(int i=1;i<=n;i++)
	{
		int q=digit[i]-48;
		int p=digit[i-1]-48;
		if(q>0 && q<=26)
			decodings[i+1]=decodings[i];
		if((q + p*10)>0 && (q + p*10) <=26)
			decodings[i+1] +=decodings[i-1];
	}
	return decodings[n];
}
//main program
int main()
{
	char digit[20];
	cout<<"Input: ";
	//user input
	gets(digit);
	int n = strlen(digit);
	//calling function and printing output
	cout<<"Number of decoding of the sequence "<<digit<<" are "<<countDecoding(digit,n);
	return 0;
}
Output:
Input: 121
Number of decoding of the sequence 121 are 3