Verbal Arithmetic Puzzle

Hard
1586.

Verbal Arithmetic Puzzle

Verbal Arithmetic Puzzle is a hard coding problem on arrays, strings and math, asked in Google and Atlassian interviews.

A cryptarithm: every uppercase letter stands for a decimal digit. Decide whether the letters can be assigned digits so that the sum of the numbers spelled by words equals the number spelled by result.

The assignment must follow these rules:

  • Each letter gets one digit, and different letters get different digits.
  • No number may have a leading zero: the first letter of any word (or of result) that is longer than one letter cannot be 0. A one-letter word may be 0.

Return true if such an assignment exists.

Example 1

Input
words = ["TO","GO"], result = "OUT"
Output
true
Explanation
T = 2, O = 1, G = 8, U = 0: 21 + 81 = 102.

Example 2

Input
words = ["A","B"], result = "CDE"
Output
false
Explanation
Two digits add up to at most 18, never a three-digit number.

Example 3

Input
words = ["SEND","MORE"], result = "MONEY"
Output
true
Explanation
9567 + 1085 = 10652.

Constraints

  • 2 <= words.length <= 5
  • 1 <= words[i].length, result.length <= 7
  • words[i] and result consist of uppercase English letters
  • At most 10 different letters appear in the whole puzzle
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} result
 * @return {boolean}
 */
var isSolvable = function(words, result) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Verbal Arithmetic Puzzle — Solution in Python, Java & C++

Verbal Arithmetic Puzzle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Verbal Arithmetic Puzzle is a hard coding problem on arrays, strings and math, asked in Google and Atlassian interviews.

Problem statement

A cryptarithm: every uppercase letter stands for a decimal digit. Decide whether the letters can be assigned digits so that the sum of the numbers spelled by words equals the number spelled by result.

The assignment must follow these rules:

  • Each letter gets one digit, and different letters get different digits.
  • No number may have a leading zero: the first letter of any word (or of result) that is longer than one letter cannot be 0. A one-letter word may be 0.

Return true if such an assignment exists.

Example 1

Input: words = ["TO","GO"], result = "OUT"
Output: true
Explanation: T = 2, O = 1, G = 8, U = 0: 21 + 81 = 102.

Example 2

Input: words = ["A","B"], result = "CDE"
Output: false
Explanation: Two digits add up to at most 18, never a three-digit number.

Example 3

Input: words = ["SEND","MORE"], result = "MONEY"
Output: true
Explanation: 9567 + 1085 = 10652.

Constraints

  • 2 <= words.length <= 5
  • 1 <= words[i].length, result.length <= 7
  • words[i] and result consist of uppercase English letters
  • At most 10 different letters appear in the whole puzzle

Hints for Verbal Arithmetic Puzzle

  1. Hint 1

    Trying all digit assignments is up to 10! ≈ 3.6 million per puzzle. Prune earlier by checking the sum column by column, as you would on paper.

  2. Hint 2

    Process the units column first: go through the words' letters in that column (assigning a digit to any unseen letter), add the carry, and the units digit of the column sum is forced for the result's letter.

  3. Hint 3

    If the result letter is already assigned a different digit — or the forced digit is taken by another letter — the branch dies right there. After the last column the carry must be 0. Also: a word longer than result can never work.

How to solve Verbal Arithmetic Puzzle

Simulate column addition from right to left while assigning digits lazily. Each result letter's digit is forced by the column sum, so most wrong partial assignments are rejected after a single column.

Approach

  1. If any word is longer than result, return false. Mark the first letter of every word or result with length > 1 as non-zero.
  2. solve(col, row, sum): if col == len(result), succeed exactly when sum == 0 (no carry left).
  3. While row points at a word: if the word has no digit in this column, move to the next row; if its letter is assigned, add its digit; otherwise try every free digit (not 0 for a leading letter), add it and recurse on the next row.
  4. When row reaches the result: the needed digit is sum % 10. If the result letter is assigned it must match; otherwise the digit must be free (and non-zero if the letter is leading) — assign it. Continue with solve(col + 1, 0, sum / 10).
  5. Undo every assignment when backtracking.

Why it works

Column addition is exactly how the sum is computed: the digit of result at a column is the column total modulo 10 and the rest is carried. By deciding letters in the order the paper algorithm reads them, every constraint is checked as soon as all of its letters are known, and the search still covers every injective assignment, so it answers correctly.

Complexity

  • Time — O(10!) worst case; far smaller with column pruning
  • Space — O(number of letters + columns)

Pitfalls

  • A one-letter word or result may be 0; only multi-letter numbers forbid a leading zero.
  • Without the final carry == 0 check, sums that overflow result look valid.
  • A letter can appear in several words and in result; it must get the same digit everywhere.

Reference solution

Python

from typing import List

def isSolvable(words: List[str], result: str) -> bool:
    L = len(result)
    if any(len(w) > L for w in words):
        return False
    W = len(words)
    assign = [-1] * 26
    used = [False] * 10
    lead = [False] * 26
    for s in words + [result]:
        if len(s) > 1:
            lead[ord(s[0]) - 65] = True

    def solve(col, row, total):
        if col == L:
            return total == 0
        if row == W:
            rc = ord(result[L - 1 - col]) - 65
            d = total % 10
            if assign[rc] >= 0:
                return assign[rc] == d and solve(col + 1, 0, total // 10)
            if used[d] or (d == 0 and lead[rc]):
                return False
            assign[rc] = d
            used[d] = True
            ok = solve(col + 1, 0, total // 10)
            assign[rc] = -1
            used[d] = False
            return ok
        w = words[row]
        if col >= len(w):
            return solve(col, row + 1, total)
        c = ord(w[len(w) - 1 - col]) - 65
        if assign[c] >= 0:
            return solve(col, row + 1, total + assign[c])
        for d in range(10):
            if used[d] or (d == 0 and lead[c]):
                continue
            assign[c] = d
            used[d] = True
            ok = solve(col, row + 1, total + d)
            assign[c] = -1
            used[d] = False
            if ok:
                return True
        return False

    return solve(0, 0, 0)

Java

static int[] vaAssign = new int[26];
static boolean[] vaUsed = new boolean[10];
static boolean[] vaLead = new boolean[26];
static String[] vaWords;
static String vaResult;

public static boolean isSolvable(String[] words, String result) {
    int L = result.length();
    for (String w : words) if (w.length() > L) return false;
    Arrays.fill(vaAssign, -1);
    Arrays.fill(vaUsed, false);
    Arrays.fill(vaLead, false);
    for (String w : words) if (w.length() > 1) vaLead[w.charAt(0) - 'A'] = true;
    if (L > 1) vaLead[result.charAt(0) - 'A'] = true;
    vaWords = words;
    vaResult = result;
    return vaSolve(0, 0, 0);
}

static boolean vaSolve(int col, int row, int sum) {
    int L = vaResult.length();
    if (col == L) return sum == 0;
    if (row == vaWords.length) {
        int rc = vaResult.charAt(L - 1 - col) - 'A';
        int d = sum % 10;
        if (vaAssign[rc] >= 0) return vaAssign[rc] == d && vaSolve(col + 1, 0, sum / 10);
        if (vaUsed[d] || (d == 0 && vaLead[rc])) return false;
        vaAssign[rc] = d;
        vaUsed[d] = true;
        boolean ok = vaSolve(col + 1, 0, sum / 10);
        vaAssign[rc] = -1;
        vaUsed[d] = false;
        return ok;
    }
    String w = vaWords[row];
    if (col >= w.length()) return vaSolve(col, row + 1, sum);
    int c = w.charAt(w.length() - 1 - col) - 'A';
    if (vaAssign[c] >= 0) return vaSolve(col, row + 1, sum + vaAssign[c]);
    for (int d = 0; d <= 9; d++) {
        if (vaUsed[d] || (d == 0 && vaLead[c])) continue;
        vaAssign[c] = d;
        vaUsed[d] = true;
        boolean ok = vaSolve(col, row + 1, sum + d);
        vaAssign[c] = -1;
        vaUsed[d] = false;
        if (ok) return true;
    }
    return false;
}

C++

struct VerbalState {
    vector<string> words;
    string result;
    int assign[26];
    bool used[10];
    bool lead[26];
};

bool verbalSolve(VerbalState& st, int col, int row, int sum) {
    int L = st.result.size();
    if (col == L) return sum == 0;
    if (row == (int)st.words.size()) {
        int rc = st.result[L - 1 - col] - 'A';
        int d = sum % 10;
        if (st.assign[rc] >= 0) return st.assign[rc] == d && verbalSolve(st, col + 1, 0, sum / 10);
        if (st.used[d] || (d == 0 && st.lead[rc])) return false;
        st.assign[rc] = d;
        st.used[d] = true;
        bool ok = verbalSolve(st, col + 1, 0, sum / 10);
        st.assign[rc] = -1;
        st.used[d] = false;
        return ok;
    }
    const string& w = st.words[row];
    if (col >= (int)w.size()) return verbalSolve(st, col, row + 1, sum);
    int c = w[w.size() - 1 - col] - 'A';
    if (st.assign[c] >= 0) return verbalSolve(st, col, row + 1, sum + st.assign[c]);
    for (int d = 0; d <= 9; d++) {
        if (st.used[d] || (d == 0 && st.lead[c])) continue;
        st.assign[c] = d;
        st.used[d] = true;
        bool ok = verbalSolve(st, col, row + 1, sum + d);
        st.assign[c] = -1;
        st.used[d] = false;
        if (ok) return true;
    }
    return false;
}

bool isSolvable(vector<string>& words, string result) {
    for (auto& w : words) if (w.size() > result.size()) return false;
    VerbalState st;
    st.words = words;
    st.result = result;
    for (int i = 0; i < 26; i++) { st.assign[i] = -1; st.lead[i] = false; }
    for (int i = 0; i < 10; i++) st.used[i] = false;
    for (auto& w : words) if (w.size() > 1) st.lead[w[0] - 'A'] = true;
    if (result.size() > 1) st.lead[result[0] - 'A'] = true;
    return verbalSolve(st, 0, 0, 0);
}

JavaScript

var isSolvable = function(words, result) {
    var L = result.length;
    var W = words.length;
    for (var w = 0; w < W; w++) if (words[w].length > L) return false;
    var assign = new Array(26).fill(-1);
    var used = new Array(10).fill(false);
    var lead = new Array(26).fill(false);
    var rows = words.concat([result]);
    for (var r = 0; r < rows.length; r++) if (rows[r].length > 1) lead[rows[r].charCodeAt(0) - 65] = true;
    var solve = function(col, row, sum) {
        if (col === L) return sum === 0;
        if (row === W) {
            var rc = result.charCodeAt(L - 1 - col) - 65;
            var d = sum % 10;
            var carry = Math.floor(sum / 10);
            if (assign[rc] >= 0) return assign[rc] === d && solve(col + 1, 0, carry);
            if (used[d] || (d === 0 && lead[rc])) return false;
            assign[rc] = d;
            used[d] = true;
            var ok = solve(col + 1, 0, carry);
            assign[rc] = -1;
            used[d] = false;
            return ok;
        }
        var word = words[row];
        if (col >= word.length) return solve(col, row + 1, sum);
        var c = word.charCodeAt(word.length - 1 - col) - 65;
        if (assign[c] >= 0) return solve(col, row + 1, sum + assign[c]);
        for (var dd = 0; dd <= 9; dd++) {
            if (used[dd] || (dd === 0 && lead[c])) continue;
            assign[c] = dd;
            used[dd] = true;
            var good = solve(col, row + 1, sum + dd);
            assign[c] = -1;
            used[dd] = false;
            if (good) return true;
        }
        return false;
    };
    return solve(0, 0, 0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings