We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Verbal Arithmetic Puzzle

Difficulty: Hard

Problem Description

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.

Key Insights

  • Each unique character represents a unique digit in the range of 0-9.
  • The constraints ensure that the maximum number of unique characters is 10.
  • Backtracking can be used to try different combinations of digit assignments to characters.
  • Leading characters of words cannot be assigned the digit 0.

Space and Time Complexity

Time Complexity: O(10!) - In the worst case, we might need to check all permutations of digit assignments for 10 characters. Space Complexity: O(1) - The space used is constant, as the maximum number of unique characters is 10.

Solution

This problem can be solved using a backtracking approach. We will recursively try to assign digits to characters, ensuring that we do not violate the constraints (no leading zeros, unique digits). For each assignment, we will compute the corresponding numerical values of the words and check if they satisfy the equation.

  1. Identify unique characters from the input words and result.
  2. Use a backtracking algorithm to assign digits to these characters.
  3. Check if the current assignment results in a valid equation.
  4. If a valid assignment is found, return true; otherwise, continue searching until all possibilities are exhausted.

Code Solutions

def is_solvable(words, result):
    from itertools import permutations

    # Get unique characters
    unique_chars = set(''.join(words) + result)
    if len(unique_chars) > 10:
        return False

    # Create a mapping of characters to their respective indices
    char_to_index = {char: i for i, char in enumerate(unique_chars)}

    # Try all permutations of digits for the unique characters
    for perm in permutations(range(10), len(unique_chars)):
        # Create a mapping from characters to digits
        char_to_digit = {char: perm[char_to_index[char]] for char in unique_chars}

        # Check for leading zeros
        if any(char_to_digit[word[0]] == 0 for word in words + [result]):
            continue

        # Calculate the sum of words
        total = sum(int(''.join(str(char_to_digit[char]) for char in word)) for word in words)
        # Calculate the result number
        expected_result = int(''.join(str(char_to_digit[char]) for char in result))

        if total == expected_result:
            return True

    return False
← Back to All Questions