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
CRYPTARITHMETIC
When people complain of your complexity, they fail to
remember that they made fun of your simplicity.
~Michael Bassey Johnson
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
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.
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
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.
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.
java; true";
main() Function
solution() function
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.
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.
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.
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.
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.