Find the possible number of decodings of a given digit sequence | faceprep

Program to find the possible number of decodings of a given digit sequence is discussed here. Given a digit sequence, find the number of possible decodings of the given digit sequence.

Let ‘A’ represent 1 , ‘B’ represent 2, and so on. 

For example,

Input: digits[] = “123”
Output: 3
/* The possible decodings are “ABC”, “LC”, “AW” */

Input: digits[] = “121”
Output: 3
/* The possible decodings are “ABA”, “AU”, “LA” */

Algorithm to find the possible number of decodings of a given digit sequence

  • Input the digit sequence.
  • Initialize count = 0.
  • If the last digit is non-zero, recur for the next remaining (n-1) digits and then add the result to the total count.
  • If the last two digits form a valid character (or smaller than 27), recur for the remaining (n-2) digits and add the result to total count.

Program to find the possible number of decodings of a given digit sequence is given below.

/* C program find the possible number of decodings of a given digit sequence */

#include <stdio.h>
#include <string.h>

int count_decoding_digits(char *digits, int n)
{
int count[n+1]; // An array to store results of subproblems
count[0] = 1;
count[1] = 1;

for (int i = 2; i <= n; i++)
{
count[i] = 0;

// If the last digit != 0, then last digit must add to the number of words
if (digits[i-1] > ‘0’)
count[i] = count[i-1];

// If second last digit is smaller than 2 and last digit is smaller than 7, then last two digits form a valid character
if (digits[i-2] == ‘1’ || (digits[i-2] == ‘2’ && digits[i-1] < ‘7’) )
count[i] += count[i-2];
}
return count[n];
}

int main()
{
char digits[15];
printf(“\nEnter the digit sequence : “);
gets(digits);
int n = strlen(digits);
printf(“\nPossible count of decoding of the sequence : %d\n”, count_decoding_digits(digits, n));
return 0;
}

/* C++ program find the possible number of decodings of a given digit sequence */

#include <iostream>
#include <cstring>
using namespace std;

int count_decoding_digits(char *digits, int n)
{
int count[n+1]; // An array to store results of subproblems
count[0] = 1;
count[1] = 1;

for (int i = 2; i <= n; i++)
{
count[i] = 0;

// If the last digit != 0, then last digit must add to the number of words
if (digits[i-1] > ‘0’)
count[i] = count[i-1];

// If second last digit is smaller than 2 and last digit is smaller than 7, then last two digits form a valid character
if (digits[i-2] == ‘1’ || (digits[i-2] == ‘2’ && digits[i-1] < ‘7’) )
count[i] += count[i-2];
}
return count[n];
}

int main()
{
char digits[15];
cout << “\nEnter the digit sequence : “;
cin >> digits;
int n = strlen(digits);
cout << “\nPossible count of decoding of the sequence : ” << count_decoding_digits(digits, n) << endl;
return 0;
}

/* Java program find the possible number of decodings of a given digit sequence */

import java.util.*;
public class Main
{
static int count_decoding_digits(char digits[], int n)
{
int[] count = new int[n+1]; // An array to store results of subproblems
count[0] = 1;
count[1] = 1;

for (int i = 2; i <= n; i++)
{
count[i] = 0;

// If the last digit != 0, then last digit must add to the number of words
if (digits[i-1] > ‘0’)
count[i] = count[i-1];

// If second last digit is smaller than 2 and last digit is smaller than 7, then last two digits form a valid character
if (digits[i-2] == ‘1’ || (digits[i-2] == ‘2’ && digits[i-1] < ‘7’) )
count[i] += count[i-2];
}
return count[n];
}

public static void main(String[] args)
{
char digits[] = {‘1’, ‘2’, ‘3’};
System.out.print(“\nEnter the points per move : “);
int n = digits.length;
System.out.print(“\nPossible count of decoding of the sequence : ” + count_decoding_digits(digits, n));
}
}

# Python program find the possible number of decodings of a given digit sequence

def count_possible_decodings(digits, n):

count = [0] * (n + 1); # A table to store results of subproblems
count[0] = 1;
count[1] = 1;

for i in range(2, n + 1):

count[i] = 0;

# If the last digit is not 0, then last digit must add to the number of words
if (digits[i – 1] > ‘0’):
count[i] = count[i – 1];

# If second last digit is smaller than 2 and last digit is smaller than 7, then last two digits form a valid character
if (digits[i – 2] == ‘1’ or
(digits[i – 2] == ‘2’ and
digits[i – 1] < ‘7’) ):
count[i] += count[i – 2];

return count[n];

digits = “1234”;
n = len(digits);
print(“Count is” , count_possible_decodings(digits, n));

Output:

find the possible number of decodings of a given digit sequence