Cryptarithmetic

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given three strings s1, s2 and s3.
2. First two are supposed to add and form third. s1 + s2 = s3
3. You have to map each individual character to a digit, so that the above equation holds true.

Note -> Check out the question video and write the recursive code as it is intended without
changing the signature. The judge can't force you but intends you to teach a concept.
Input Format
Three strings
s1
s2
s3
Output Format
Check the sample output and question video
Question Video
Constraints
1 <= length of s1,s2,s3 <= 10
Sample Input
team
pep
toppr
Sample Output
a-3 e-9 m-4 o-1 p-2 r-6 t-0 
a-3 e-9 m-5 o-1 p-2 r-7 t-0
a-3 e-9 m-6 o-1 p-2 r-8 t-0
a-4 e-9 m-2 o-1 p-3 r-5 t-0
a-4 e-9 m-5 o-1 p-3 r-8 t-0
a-5 e-9 m-2 o-1 p-4 r-6 t-0
a-5 e-9 m-3 o-1 p-4 r-7 t-0
a-6 e-9 m-2 o-1 p-5 r-7 t-0
a-6 e-9 m-3 o-1 p-5 r-8 t-0
a-7 e-9 m-2 o-1 p-6 r-8 t-0


  • Editorial

    Let us go through the rules again:

    Each character must be mapped with a number between 0 to 9. Each number can be used once only. For example - if 9 is mapped to 'a', then it cannot be mapped to any other letter. There will be one to one mapping..

    We can observe that we can solve this question by recursion and backtracking. We will first find a string that contains unique characters of s1,s2 and s3 using hashmap. Then we will assign every number from 0 to 9 to every character of this unique string. If we reach at the end of this string we will check whether the condition s1 + s2 = s3 holds true. If it is true, we will display the answer and return.

    To maintain the one to one mapping, we will use an auxiliary Boolean array of size 10 to store whether the current number has been used or not. If it is used we will mark that position as true in pre-order and for the further calls, we will not be able to use it again. In post-order we will unmark so it can be used again. Also, we will use a hashmap to store what value has been assigned to a character. Initially hashmap will contain every unique character as a key and -1 as a value for all the keys. In pre-order, we will mark the number we assigned to that number as value and in post order we will assign -1 again.

    Signature:

    public static void solution(String unique, int idx, HashMap
                                     charIntMap, boolean[] usedNumbers,
                                                String s1, String s2, String s3) {

    unique - substring containing all the unique characters of s1,s2 and s3.

    idx - current index

    charIntMap - Hashmap that will have initially all the characters of unique substring as key and -1 as value.

    usedNumbers - an auxiliary array to store which numbers from 0 to 9 have been used.

    s1,s2 and s3 - input substring

    Code:

    public static void solution(String unique, int idx, HashMap

    charIntMap, boolean[] usedNumbers, String s1, String s2, String s3) { if (idx == unique.length()) { int num1 = getNum(s1, charIntMap); int num2 = getNum(s2, charIntMap); int num3 = getNum(s3, charIntMap); if (num1 + num2 == num3) { for (int i = 0; i < 26; i++) { char ch = (char) ('a' + i); if (charIntMap.containsKey(ch)) { System.out.print(ch + "-" + charIntMap.get(ch) + " "); } } System.out.println(); } return; } char ch = unique.charAt(idx); for (int num = 0; num <= 9; num++) { if (usedNumbers[num] == false) { usedNumbers[num] = true; charIntMap.put(ch, num); solution(unique, idx + 1, charIntMap, usedNumbers, s1, s2, s3); charIntMap.put(ch, -1); usedNumbers[num] = false; } } } public static int getNum(String s, HashMap

    charIntMap){ String num = ""; for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); num += charIntMap.get(ch); } return Integer.parseInt(num); }

    java falseCode Explained:

    In recursion, the characters of unique string will be at level.

    We will assign each character a number from 0 to 9 and mark the number we visited as true and mark the number we assigned to the character in hashmap in pre-order. We will call recursive function for the next level and in post-order we will unmark the number we used and put -1 for that character in hashmap.

    When index will be equal to the length of the unique substring, we will check whether the s1 + s2 == s3. If it is, we will print all the values we assigned to the character lexicographically.

    We will return as all the characters have been used value.

    Base Case:

    When idx will be equal to the length of the unique substring, then we will check whether the numbers we assigned satisfy the given condition or not. To check that we will iterate throught the s1 and generate the number we will get from it. Similarly, for s2 and s3. If the numbers returned satisfy the condition, we will print the answer in lexicographical manner.

    Code to generate the respective numbers :

    public static int getNum(String s, HashMap charIntMap){
                                         String num = "";
                                    
                                         for(int i = 0; i < s.length(); i++){
                                      char ch = s.charAt(i);
                                      num += charIntMap.get(ch);
                                         }
                                         return Integer.parseInt(num);
                                    }

    Dry Run:

    Input s1 = SEND, s2 = MORE and s3 = MONEY

    Unique string will be SENDMOREY

    This is how recursion tree will look like:

    We see that each unique character is assigned a number from 0 to 9 and at next level, the number assigned before is not used again.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name