Java Code to Count Possible Decoding Of A Given Digit Sequence

July 1, 2023

Possible decoding of a given digit sequence in Java

Count Possible Decoding Of A Given Digit Sequence in Java

Here we will discuss how to count all the possible decoding of a given digit sequence in Java. Before counting the number of decodings first let’s see how the numbers are assumed to be coded. The decoding programs are the most possible questions asked and are largely practiced in Java programming. The program counts the number of possible decoding’s of the entered digit by the user of the given sequence.

Explanation

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 decoding’s of the entered digit by the user of the given sequence.
For example :- if the digit sequence is “12” then there are two possible decoding’s 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 decoding’s of sequence 131 is 2.

Algorithm

  • Initialize a array cnt of size 1 + length of input and store 1 at 0 & 1 position
  • Iterate from 2 to a using variable k
  • If the last digit not equal to 0, then last digit must added to the number of words if (dig[k-1] > ‘0’)
  • In case second last digit is smaller than 2 and last digit is smaller than 7, then last two digits form a valid character
  • Print cnt[a]
Count Possible Decoding java

Java code

Run 
import java.io.*;

public class Main
{
    public static int cnt_decoding_digits(char[] dig, int a)
    {
        int cnt[] = new int[a+ 1];

        cnt[0] = 1;

        cnt[1] = 1;

        for (int k = 2; k <= a; k++) 
        { 
            cnt[k] = 0; 

            cnt[k] = cnt[k-1];

            if (dig[k-2] == '1' || (dig[k-2] == '2' && dig[k-1] < '7') )

                cnt[k] += cnt[k-2];
        }
        return cnt[a];
    }
    public static void main (String[] args)
    {
        String s="123";

        char[] dig= s.toCharArray();

        System.out.println(cnt_decoding_digits(dig, 3));
    }
}

Output

Enter the sequence : 123
Possible count of decoding of the sequence : 3

Java code

Run 
public class Main {

    // Function to count possible decodings
    public static int countDecodings(String digits) {
        int n = digits.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            // Check if the current digit is a valid single-digit number
            if (digits.charAt(i - 1) != '0') {
                dp[i] = dp[i - 1];
            }

            // Check if the current and previous digit form a valid double-digit number
            if (digits.charAt(i - 2) == '1' || (digits.charAt(i - 2) == '2' && digits.charAt(i - 1) <= '6')) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        String digits = "12122";
        int possibleDecodings = countDecodings(digits);
        System.out.println("Number of possible decodings: " + possibleDecodings);
    }
}

Output

Number of possible decodings: 8

Here’s how the code works:

  • It initializes an array dp of size n + 1, where n is the length of the input string digits. This array will store the intermediate results of subproblems.
    It sets dp[0] and dp[1] to 1 since there is only one way to decode an empty string or a single-digit number.
    • It iterates over the digits starting from the index 2 up to n.
      For each digit at index i, it checks if the digit is a valid single-digit number (i.e., not ‘0’). If so, it assigns dp[i] the value of dp[i – 1] since the current digit can be decoded independently.
    • It then checks if the current digit and the previous digit form a valid double-digit number. It does this by checking if the previous digit is ‘1’ or ‘2’ and the current digit is less than or equal to ‘6’. If this condition is met, it adds the value of dp[i – 2] to dp[i]. This is because the current digit can be decoded along with the previous digit to form a valid two-digit number.
    • Finally, it returns the value of dp[n], which represents the total number of possible decodings for the given string of digits.
    • In the main function, a sample input string “12122” is provided, and the countDecodings function is called to calculate the number of possible decodings. The result is then printed to the console.
  • If you run this code, it will output: “Number of possible decodings: 8” for the input string “12122”.
 
 

Addition of two fractions

Replace all 0’s with 1 in a given integer

Can a number be expressed as a sum of two prime numbers

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

6 comments on “Java Code to Count Possible Decoding Of A Given Digit Sequence”


  • Navya

    the given code is working good only for certain inputs and its not working for single digits etc.,


    • PrepInsta Support

      Hi Navya, code is working for aLL SINGLE digits inout. Still we are adding one more code to take double digits input as well.
      Thank you for response.


  • manicampusplacements

    public class Main {
    public static int countDecodings(String digits) {
    int n = digits.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i = 1 && first = 10 && second <= 26) {
    dp[i] += dp[i – 2];
    System.out.println(dp[i]);
    }
    }

    return dp[n];
    }

    public static void main(String[] args) {
    String digits = "1234";
    int count = countDecodings(digits);
    System.out.println("Number of possible decodings: " + count);
    }
    }


  • KUNCHA

    public class Main
    {

    public static void main(String[] args) {
    int num = 1221;
    int decoding = 1;
    while(String.valueOf(num).length() >= 2){
    int digits = num%100;
    if(digits =1){
    decoding++;
    }
    num = num/10;
    }
    System.out.println(decoding);
    }
    }
    //any mistake please comment down.


  • Ankitha

    public class DecodeCount {
    public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n= sc.nextInt();
    int l=0; int count=1;
    while(n>9) {
    l=n%100;
    if(l<=26) {
    count++;
    }
    n=n/10;
    }
    System.out.println(count);
    }
    }


  • 06_Animesh

    import java.util.*;
    import java.lang.*;
    import java.io.*;

    class Main
    {
    static List arr = new ArrayList();
    public static void main (String[] args) throws java.lang.Exception
    {
    // your code goes here
    try{
    //scanner class object creation
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String str = Integer.toString(n);
    String output = “”;
    possibleCode(str.substring(1), output + str.charAt(0));
    System.out.println(arr.size()-1);
    }catch(Exception e){
    return;
    }
    }

    public static void possibleCode(String str, String output){
    if(str.length()==0){
    arr.add(output);
    return;
    }
    possibleCode(str.substring(1), output+ “_”+str.charAt(0));
    possibleCode(str.substring(1), output+str.charAt(0));
    return;
    }
    }