C++ Code to Count Possible Decoding Of A Given Digit Sequence

November 2, 2021

Count possible decodings of a given digit sequence:-

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.

Possible decoding of a digit sequence

Algorithm

  • Step 1: Start
  • Step 2: User is required to insert a digit sequence as an input
  • Step 3: Set count = 0
  • Step 4: If the last number is not a zero, then return for the next remaining (n-1) numbers and add the results then to the total count.
  • Step 5: If the last two digits form a valid variable (or smaller than 27), return for the remaining (n-2) numbers and add the outcome to the total calculation.
  •  Step 6: Stop

C++ Code:-

#include<stdio.h>
#include<math.h>

int cnt_decoding_digits(char *dig, int a)
{
// Initializing an array to store results 
int cnt[a+1]; 
cnt[0] = 1;
cnt[1] = 1;

for (int k = 2; k <= a; k++) { cnt[k] = 0; 
// If the last digit not equal to 0, then last digit must added to the number of words if (dig[k-1] > '0')
cnt[k] = cnt[k-1];

// In case second last digit is smaller than 2 and last digit is smaller than 7, then last two digits form a valid character
if (dig[k-2] == '1' || (dig[k-2] == '2' && dig[k-1] < '7') )
cnt[k] += cnt[k-2];
}
return cnt[a];
}

int main()
{
char dig[15];
cout<<"\n Enter the sequence : ";
gets(dig);
int a = strlen(dig);
cout<<"\n Possible count of decoding of the sequence :"<<cnt_decoding_digits(dig, a);
return 0;
}
Output:
Insert the digit sequence: 123456
Possible count of decoding of the sequence: 3