Skip to main content
Talentd

Verbal Arithmetic Puzzle - Solution & Explanation

HardArrayMathStringBacktracking12 min readAsked at: Wells Fargo, Atlassian, Google
Practice this problem

Problem Statement

Given an equation, represented by words on the left side and the result on the right side.

You need to check if the equation is solvable under the following rules:

  • Each character is decoded as one digit (0 - 9).
  • No two characters can map to the same digit.
  • Each words[i] and result are decoded as one number without leading zeros.
  • Sum of numbers on the left side (words) will equal to the number on the right side (result).

Return true if the equation is solvable, otherwise return false.

 

Example 1:

Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: Map 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
Such that: "SEND" + "MORE" = "MONEY" ,  9567 + 1085 = 10652

Example 2:

Input: words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
Output: true
Explanation: Map 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
Such that: "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214

Example 3:

Input: words = ["LEET","CODE"], result = "POINT"
Output: false
Explanation: There is no possible mapping to satisfy the equation, so we return false.
Note that two different characters cannot map to the same digit.

 

Constraints:

  • 2 <= words.length <= 5
  • 1 <= words[i].length, result.length <= 7
  • words[i], result contain only uppercase English letters.
  • The number of different characters used in the expression is at most 10.

Approach Overview

Problem Overview: You are given several words representing numbers where each character maps to a unique digit (0ā€“9). The goal is to determine whether a digit assignment exists such that the sum of the first nā€‘1 words equals the final word. Leading characters cannot map to zero, and every letter must map to a distinct digit.

Approach 1: Backtracking Search (Exponential, ~O(10!) time, O(1) space)

This approach treats the puzzle as a digit assignment problem. First collect all unique characters across the input words. Then recursively assign digits from 0ā€“9 while maintaining a used set so no digit is reused. After assigning digits to all characters, convert each word into a number and check whether the arithmetic equation holds. The key pruning rule prevents assigning 0 to leading characters. This brute-force backtracking search explores permutations of digits but prunes many invalid states early.

Approach 2: Constraint Satisfaction with Bit Masking (Optimized Backtracking, ~O(10!) worst case, O(1) space)

A more structured solution evaluates the equation column by column from right to left, similar to manual addition. Instead of constructing full numbers, maintain the running column sum and propagate carry values during recursion. A bit mask tracks which digits are already assigned, enabling constant-time digit availability checks. This turns the problem into a constraint satisfaction system where partial assignments are validated immediately. Early pruning dramatically reduces the search space because invalid column sums are discarded before exploring deeper states. This method combines ideas from math, string processing, and constraint-based backtracking.

Recommended for interviews: Start by explaining the basic backtracking permutation idea since it demonstrates understanding of the search space and constraints. Then move to the column-wise constraint approach with bit masking. Interviewers prefer this optimized strategy because it prunes invalid assignments early and models the arithmetic addition directly, which significantly reduces unnecessary recursion.

Approach 1: Backtracking Approach

The backtracking approach involves recursively trying to assign digits to each character ensuring all constraints are met. By assigning digits to characters one by one, we calculate if they sum to the required result, backtracking if an assignment leads to an invalid state.

This solution explores different configurations and checks their validity, making it suitable due to the limited number of possible mappings.

This function begins by identifying all unique characters present in the words and result. If there are more than 10 unique characters, it's impossible to find a unique digit for each character, so it returns False immediately.

The function goes through all possible permutations of digits for these characters, ensuring no character that leads a word is assigned a zero (to avoid leading zeros). If any permutation yields a valid sum, True is returned. Otherwise, the function returns False after checking all permutations.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(10^n) where n is the number of unique characters, considering the worst possibility of evaluating all permutations.
Space Complexity: O(1) as transformations exist within constant space primarily bound by auxiliary data structures.

Try this approach in the editor ā†’

Approach 2: Constraint Satisfaction with Bit Masking

The bit masking approach iteratively assigns digits to characters using bit masks to represent remaining available digits instead of checking conventional arrays. This method helps speed up operations by reducing assignments overhead and allows faster constraint checks.

This C++ solution uses standard library features to implement a bit masking technique for character-to-digit assignments, with recursive depth control to evaluate valid mappings.
It represents each character using its ASCII value and calculates potential word sums, verifying their equivalency to result values and returning True or False.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(10^n), consistent with permutations of n characters.
Space Complexity: O(1), largely leveraging existing data structures and small auxiliary vectors.

Try this approach in the editor ā†’

Approach 3: Default Approach

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(10^n) where n is the number of unique characters, considering the worst possibility of evaluating all permutations.
Space Complexity: O(1) as transformations exist within constant space primarily bound by auxiliary data structures.

Constraint Satisfaction with Bit Masking

Time Complexity: O(10^n), consistent with permutations of n characters.
Space Complexity: O(1), largely leveraging existing data structures and small auxiliary vectors.

Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking Digit AssignmentO(10!)O(1)Good starting point to explain brute-force search and permutation generation
Constraint Satisfaction with Bit MaskingO(10!) worst case (heavily pruned)O(1)Preferred approach for interviews and competitive coding due to strong pruning

Video Solution

Leetcode 1307: Verbal Arithmetic Puzzle (Leetcode Hard) ā€¢ Algorithms Casts ā€¢ 5,049 views views

Watch 4 more video solutions ā†’

Frequently Asked Questions

Is Verbal Arithmetic Puzzle easy or hard?
Verbal Arithmetic Puzzle is classified as a Hard problem because it combines recursion, constraint satisfaction, and arithmetic reasoning. Efficient solutions require careful pruning strategies rather than simple brute-force permutations.
Verbal Arithmetic Puzzle Python/Java solution
Python solutions usually implement recursive backtracking with dictionaries for character-digit mapping. Java and C++ implementations often add bit masking for faster digit availability checks and column-wise constraint validation to reduce unnecessary recursion.
How to solve Verbal Arithmetic Puzzle in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of digit assignments. The optimal strategy uses backtracking with constraint pruning, which has factorial worst-case complexity but performs well due to early elimination of invalid assignments.
What is the best approach for Verbal Arithmetic Puzzle?
The most effective solution models the puzzle as a constraint satisfaction problem using backtracking with column-wise addition. By processing digits from right to left and validating partial sums with carry values, invalid assignments are pruned early. A bit mask tracks used digits efficiently, reducing the search space compared to naive permutation checks.
Is Verbal Arithmetic Puzzle asked at Google/Amazon/Meta?
Verbal arithmetic and cryptarithm problems frequently appear in interviews at companies like Google and Meta because they test recursion, constraint reasoning, and pruning strategies. Variants of this problem are common in algorithm interviews focused on backtracking and search.
What data structure is used in Verbal Arithmetic Puzzle?
Typical solutions use hash maps or arrays to store character-to-digit mappings, along with a boolean array or bit mask to track used digits. Recursion with backtracking drives the search while enforcing arithmetic constraints.
What is the time complexity of Verbal Arithmetic Puzzle?
The worst-case time complexity is O(10!) because each unique letter may be assigned a different digit from 0ā€“9. In practice, constraints such as leading-zero restrictions and column-wise validation prune most branches, making the search much faster than exploring all permutations.

Ready to solve this problem?

Practice Verbal Arithmetic Puzzle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays