5 Best Ways to Check If All Sub-Numbers Have Distinct Digit Products in Python

Rate this post

πŸ’‘ Problem Formulation: We are challenged with verifying whether every substring of a given number has a unique product of its digits. For instance, if the input number is 123, a desired output would be True because the products of the digits (1, 2, 3, 2*1, 3*1, 3*2, 3*2*1) are all distinct.

Method 1: Brute Force

This method iterates through all possible substrings of the given number, calculates the product of the digits for each substring, and checks for uniqueness. This is a straightforward approach but can be inefficient for large numbers due to its O(n^2) complexity.

Here’s an example:

def has_distinct_digit_products(number):
    products = set()
    num_str = str(number)
    for i in range(len(num_str)):
        for j in range(i+1, len(num_str) + 1):
            product = 1
            for digit in num_str[i:j]:
                product *= int(digit)
            if product in products:
                return False
            products.add(product)
    return True

print(has_distinct_digit_products(123))

Output:

True

The function has_distinct_digit_products() checks each substring of the number by using nested loops. It multiplies the digits of each substring and adds the product to a set, which inherently ensures that all products are unique. If a product is already in the set, it returns False; otherwise, after all checks, it returns True.

Method 2: Using Map and Reduce

This method involves using the map and reduce functions from the functools module to calculate the product of digits in each substring. It’s a functional programming approach that can be more concise than the brute force method.

Here’s an example:

from functools import reduce

def has_distinct_digit_products(number):
    products = set()
    num_str = str(number)
    for i in range(len(num_str)):
        for j in range(i+1, len(num_str) + 1):
            product = reduce(lambda x, y: x*y, map(int, num_str[i:j]))
            if product in products:
                return False
            products.add(product)
    return True

print(has_distinct_digit_products(123))

Output:

True

We replace the innermost loop of the brute force method with a combination of map and reduce to calculate the product. The rest of the logic remains the same: checking against a set for uniqueness and returning a Boolean value.

Method 3: Using itertools and List Comprehension

The itertools module can be utilized to efficiently generate all possible substrings. This approach is more pythonic and leverages list comprehension for a clean and compact implementation.

Here’s an example:

from itertools import combinations

def has_distinct_digit_products(number):
    num_str = str(number)
    indices = range(len(num_str) + 1)
    substrings = (num_str[i:j] for i, j in combinations(indices, 2))
    products = {reduce(lambda x, y: x * y, map(int, substring)) for substring in substrings}
    return len(products) == len(set(substrings))

print(has_distinct_digit_products(123))

Output:

True

In method 3, combinations from the itertools module is used to generate all possible pairs of start and end indices for substrings. The products are calculated within a set comprehension, and then we compare the lengths of the set of products and substrings to determine if all digit products are distinct.

Method 4: Optimized Checking with Early Exit

This method is similar to the brute force approach but includes optimization by early exiting when a repeated product is found, reducing the number of checks in cases where products repeat early.

Here’s an example:

def has_distinct_digit_products(number):
    products = set()
    num_str = str(number)
    for i in range(len(num_str)):
        for j in range(i+1, len(num_str) + 1):
            product = reduce(lambda x, y: x*y, map(int, num_str[i:j]))
            if product in products:
                return False
            products.add(product)
    return True

print(has_distinct_digit_products(123))

Output:

True

Method 4 refines the previous method by checking for the presence of the product in the set before adding it to the set. If the product already exists, it returns False immediately, providing an early exit from the function.

Bonus One-Liner Method 5: Using Generator Expression and all()

This one-liner uses a generator expression along with the all() function to check for uniqueness of the product of digits of each substring. It’s a concise and elegant solution but may be less readable for beginners.

Here’s an example:

def has_distinct_digit_products(number):
    num_str = str(number)
    return all(
        num_str[i:j].count(digit) == 1
        for i in range(len(num_str))
        for j in range(i+1, len(num_str)+1)
        for digit in num_str[i:j]
    )

print(has_distinct_digit_products(123))

Output:

True

The one-liner defines a generator expression that iterates through all substrings, and checks that each digit only occurs once in each substring. The all() function returns True if all conditions in the generator are True, ensuring all products are distinct.

Summary/Discussion

  • Method 1: Brute Force. Strength: Easy to understand and implement. Weakness: Inefficient for large numbers.
  • Method 2: Using Map and Reduce. Strength: More concise code. Weakness: Might still be considered verbose compared to other methods.
  • Method 3: Using itertools and List Comprehension. Strength: Pythonic and compact. Weakness: Requires understanding of itertools.
  • Method 4: Optimized Checking with Early Exit. Strength: More optimal than brute force. Weakness: Improvement is marginal and depends on the input.
  • Bonus Method 5: One-Liner. Strength: Extremely concise. Weakness: Can be cryptic and hard to read for those not familiar with Python idioms.