1

Verbal Arithmetic Puzzle

Difficulty: NINJA
Contributed By
Shrey Pansuria
Avg. time to solve
55 min
Success Rate
45%

Problem Statement

You are given an array of the strings “words” of size 'M' and another string “result”. You have to treat it as an equation in which the left side is represented by the array “words” and the right side is represented by the string "result". Your task is to determine whether the equation is solvable or not under the following conditions:

1. Each character is decoded as a digit in the range [0, 9].
2. Each character must have only one mapping, and every pair of characters must map to different digits.
3. Each element of the array “words” and the string “result” are decoded as one number without the leading zeros.
4. The sum of the numbers on the left-hand side (words) must equal the number on the right-hand side (result).

Note:

1) The array “words”, and the string “result” contain only the uppercase English letters.
2) The number of different characters used in the expression is at most 10.
Input Format:
The first line contains an integer T, which denotes the number of test cases or queries to be run. Then, the T test cases follow. 

The first line of each test case contains a positive integer M denoting the size of the array “words”, as described in the problem statement.

The second line of each test case contains a sequence of M space-separated strings denoting the elements of the array.

The third line of each test case contains a string denoting the result string.
Output Format:
For each test case, print in a new line "true" if the equation is solvable and "false" otherwise.

Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
2 <= M <= 5
1 <= |WORDS[i]|, |RESULT| <= 7

The number of different characters used in the expression is at most 10.

Time Limit: 1sec
Sample Input 1:
1
2
SEND MORE
MONEY
Sample Output 1:
true
Explanation Of Sample Input 1:
We can map ‘S’ -> 9, ‘E’ -> 5, ‘N’ -> 6, ‘D’ -> 7, ‘M’ -> 1, ‘O’ -> 0, ‘R’ -> 8, ‘Y’ -> 2. So, “SEND” will decode as 9567, “MORE” as 1085, and “MONEY” as 10652. Also the equation SEND + MORE = MONEY, 9567 + 1085 = 10652 will satisfy. 
Sample Input 2:
1
2
LEFT CODE
CODED
Sample Output 2:
false
Explanation Of Sample Input 2:
There is no mapping available that can satisfy the required equation.
Reset Code
Full screen
copy-code
Console