Java Code to Count Possible Decoding Of A Given Digit Sequence

July 1, 2023

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.

Way 2 of asking Question Count possible decodings of a given digit sequence -

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]

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”.

Quadrants in which a given coordinate lies

Permutations in which n people can occupy r seats in a classroom

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

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.,

0

Log in to Reply

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.

0

Log in to Reply

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);
}
}

0

Log in to Reply
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.

0

Log in to Reply
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);
}
}

1

Log in to Reply
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;
}
}

0

Log in to Reply