Redirecting to
NADOS


  Prev   Next

CRYPTARITHMETIC







When people complain of your complexity, they fail to remember that they made fun of your simplicity.
~Michael Bassey Johnson

CRYPTARITHMETIC

Good day coder. We begin with a new question in this article, "Cryptarithmetic".

We first suggest you go through the outline of the question from the problem link given below.

Important Link : Problem Link, Solution Video

Understanding The Problem:
  • You are given three strings s1, s2 and s3.
  • First two are supposed to add and form the third string i.e. s1 + s2 = s3.
  • You have to map each individual character to a digit, so that the above equation holds true.
  • No character can be assigned 2 unique digits and similarly, no digit can be mapped to 2 unique characters. Hence it is a 1:1 mapping.
  • Print every mapping in increasing order of characters which means 'a' is printed before 'b'.
  • We want you to attempt this question using recursion.

Say, we are given the input strings s1, s2 and s3 as "send", "more" and "money" respectively.

Here, we have to assign all the unique characters with the appropriate digits such that the sum of the encrypted strings, s1 and s2 is equal to the encrypted value of s3.

Figure shows us all the unique characters from the three strings that are to be assigned with digits from 0 to 9.

img

Note: The total number of unique characters from the three strings should not be greater than 10 because the mapping is 1:1 and we only have 10 digits available(0-9).

There are a lot of solutions for the above examples, let's discuss one of them.

Let the characters be assigned as shown in Figure

img

According to figure, "send"=9567, "more"=1085 and "money"=10652.

Reader, check whether adding the numbers 9567 and 1085 give us the sum as 10652.

It does! Hence, it is one of the answers.

We have to print all such mappings.

Approach:

In this problem, we first discuss the code part of the solution. After that we will be able to draw a recursion tree for the code and understand the problem better.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); String s1 = scn.nextLine(); //1 String s2 = scn.nextLine(); String s3 = scn.nextLine(); HashMap < Character, Integer > charIntMap = new HashMap<>(); //2 String unique = ""; //3 for (int i = 0; i < s1.length(); i++) { //4 if (!charIntMap.containsKey(s1.charAt(i))) { charIntMap.put(s1.charAt(i), -1); unique += s1.charAt(i); } } for (int i = 0; i < s2.length(); i++) { if (!charIntMap.containsKey(s2.charAt(i))) { charIntMap.put(s2.charAt(i), -1); unique += s2.charAt(i); } } for (int i = 0; i < s3.length(); i++) { if (!charIntMap.containsKey(s3.charAt(i))) { charIntMap.put(s3.charAt(i), -1); unique += s3.charAt(i); } } boolean[] usedNumbers = new boolean[10]; //5 solution(unique, 0, charIntMap, usedNumbers, s1, s2, s3); //6 } public static int getNum(String s, HashMap < Character,Integer > charIntMap){ String num=""; //1 for(int i=0;i < s.length();i++){ //2 num+=charIntMap.get(s.charAt(i)); } return Integer.parseInt(num); //3 } public static void solution(String unique, int idx,HashMap< Character, Integer > charIntMap, boolean[] usedNumbers,String s1, String s2, String s3) { if(idx==unique.length()){ //1 int num1=getNum(s1,charIntMap); //2 int num2=getNum(s2,charIntMap); int num3=getNum(s3,charIntMap); if(num1+num2==num3){ //3 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();//4 } return; } char ch=unique.charAt(idx); //6 for(int num=0;num< =9;num++){ if(usedNumbers[num]==false){ charIntMap.put(ch,num); usedNumbers[num]=true; solution(unique,idx+1,charIntMap,usedNumbers,s1,s2,s3); usedNumbers[num]=false; charIntMap.put(ch,-1); } } } }
java; true";

main() Function

  1. The three strings s1,s2 and s3 are taken as input.
  2. A character vs. Integer hashmap called "charIntMap" is created. We will store all the unique characters and their 1:1 mapping in this hashmap.
  3. The "unique" string stores all the unique characters of the 3 strings.
  4. We run a loop for all the characters of the string s1.
  5. If the hashmap doesn't contain a character, it gets added in the hashmap against the value '-1' which shows that that character hasn't been mapped (assigned a digit) yet. This character is then added to the "unique" string. The same process is followed for strings s2 and s3.
  6. "usedNumbers" is a boolean array which has indices from 0 to 9. If a digit has been mapped (assigned to a character), then "true" is stored against the corresponding index of that digit. Else "false" is stored for that index.
  7. We call the solution function which is responsible for getting the required mappings.
img

solution() function

  1. BASE CASE: We check if "idx" goes beyond the length of the "unique" string. If it does then it means that the mapping of all the characters is finished. But we don't know if this mapping is correct or not. To check that, the following steps (//2 to //4) are followed.
  2. We obtain the encrypted numbers for a certain mapping of the characters. The value of these encrypted numbers is stored in num1, num2 and num3 for string s1, s2 and s3 respectively.
  3. If our desired property of num1+num2=num3 holds true then we apply a loop for all the characters and check if that character is present in the hashmap or not. The purpose of applying this loop is to print all the characters in an alphabetical order.
  4. Then we simply move to the next line and return from the function for this mapping.
  5. If the mapping is not yet complete, we perform the following steps for the desired character at the index "idx" from the string "unique".
  • We try all the numbers from 0 to 9, to assign to this character by running a loop.
  • We check if the current "num" has not been assigned to some other character i.e. we check if usedNumbers[num]==false.
  • If these conditions are fulfilled then we put that character against the value "num" in the hashmap.
  • We also put "true" against the index corresponding to "num" in the array "usedNumbers" so that it isn't used again.
  • Then we have to repeat the above process for the character at the next index of the "unique" string for which a recursive call is made.
  • When we backtrack from the recursion stack, we store "false" against every digit in "usedNumbers" to indicate that it isn't in use anymore. Also, we initialize the value of the character in the hashmap as '-1'.

getNum() Function

This function returns the number equivalent of the string after mapping of all the characters has been performed.

//1 We assign 0 to an integer "num" initially.

//2 We run a loop for every character of the string parameter and the value in hashmap against every character of the string is added to "num".

//3 Now "num" stores a string of the numbers but we require an integer value of the encryption , hence the string is changed into an integer using Integer.parseInt() function.

Recursion Tree
img

The above figure depicts that we start from the first index of "unique" string i.e. 's'. This character can be assigned any number from 0 to 9. We first assign it the number 0 and hence the value for 's' is changed from -1 to 0.
Also the number 0 is marked as true.

img

Now we reach the second level for the character at the next index i.e. 'e'.
Again we write all the choices of the digits that can be assigned to it. 0 is not included in these choices because it has already been assigned to 's'.
If we assign 1 to 'e' then, it's value in the HashMap is changed and the number 1 is marked as "true" in the boolean array.
This process is continued for all the characters in the "unique" string.
After doing that, we obtain a 1:1 mapping for all the unique characters. We have to check if it satisfies our condition of num1+num2=num3.
If it does then the mapping is printed in alphabetical order.
After finishing one mapping, we backtrack from the recursion stack and initialize the character with -1 and mark it as "false" in the boolean array so that another method of mapping can be found.

We want you to go through the solution video of this problem to get an in depth understanding of this problem.

Analysis
Time Complexity

O(xl) where x= total options( or total number digits =10) and l= total levels of the recursion tree (or total unique characters, here, l=8). This means that each level has around 10 options for every unique character.
However, according to the question, if a digit is used already, it can't be used again. So effectively the time complexity here will be 10*9*8*7*6*5*4*3.

Space Complexity

O(n)
Reader, we conclude this question here and take your leave. We are going to discuss more such problems in the upcoming questions. See you then.

Cryptarithmetic
Recursion
Author: Shreeya Gupta
 
Run
Id Name