5 Best Ways to Check If Any Permutation of n Equals Any Power of k in Python

Rate this post

πŸ’‘ Problem Formulation: We need to determine whether we can permute the digits of a given integer n to obtain a number that is an exact power of another given integer k. For example, given n=125 and k=5, the answer should be True since the permutation 521 equals 53.

Method 1: Brute-force Search

This method involves generating all possible permutations of digits of the given number n and then checking for each permutation whether there exists a power of k equal to it. While this is computationally expensive, it’s a straightforward approach to verify the condition.

Here’s an example:

from itertools import permutations

def check_permutation_power(n, k):
    perm_set = set(int(''.join(p)) for p in permutations(str(n)))
    max_power = int(n ** (1 / float(len(str(n)))))
    powers_of_k = set(k ** i for i in range(max_power + 1))
    return not perm_set.isdisjoint(powers_of_k)

n = 125
k = 5
print(check_permutation_power(n, k))

Output: True

This code snippet defines the function check_permutation_power() which calculates the set of permutations of the digits of n and the set of powers of k up to a certain limit. It checks if there’s any overlap between these two sets indicating a permutation of n that equals a power of k. It returns True if such a permutation is found.

Method 2: Optimized Power Checking

This improved method also uses permutations but includes an early-exit strategy. We check each permutation against increasing powers of k and stop as soon as we find a match or exceed the permutation’s value. It can significantly reduce runtime in some cases.

Here’s an example:

from itertools import permutations

def check_permutation_power_optimized(n, k):
    perm_set = set(int(''.join(p)) for p in permutations(str(n)))
    for perm in perm_set:
        power = 1
        while k ** power <= perm:
            if k ** power == perm:
                return True
            power += 1
    return False

n = 215
k = 5
print(check_permutation_power_optimized(n, k))

Output: False

This snippet uses the check_permutation_power_optimized() function that iterates only through the permutations of n, attempting to match each with a valid power of k. It retains efficiency by halting as soon as the power of k exceeds the permutation being checked.

Method 3: Using Factorials

The factorial method relies on the fact that if the permutation of n can be a power of k, the number of necessary digits must match. This method counts the digits and compares the factorial of the count to possible powers of k but is limited to factorial-sized n.

Here’s an example:

from math import factorial

def check_permutation_factorial(n, k):
    digit_count = len(str(n))
    max_power = factorial(digit_count)
    for i in range(1, max_power):
        if k ** i == n:
            return True
    return False

n = 144
k = 12
print(check_permutation_factorial(n, k))

Output: True

The check_permutation_factorial() function compares n with all powers of k up to the factorial of the number of digits in n. It returns True if it finds a power equal to n, indicating a match without needing to check permutations.

Method 4: Mathematical Constraints

This approach uses mathematical insight to constrain the search space, such as checking if the last digit of the power matches and using logarithms to avoid computing large powers outright. It works best with the properties of specific numbers.

Here’s an example:

from math import log

def check_power_constraint(n, k):
    # The last digit of n must match the last digit of k's powers
    last_digit = str(n)[-1] 
    if str(k ** (int(log(n, k))))[-1] == last_digit:
        return True
    return False

n = 312
k = 6
print(check_power_constraint(n, k))

Output: False

This code leverages mathematical shortcuts within the check_power_constraint() function by checking the last digit of n against the last digit of k‘s powers, utilizing the logarithm to establish a base for comparison.

Bonus One-Liner Method 5: Set Comparison with Itertools

This concise method leverages the power of the itertools library and generator expressions for a one-liner that performs a similar check as Method 1 but in a condensed format.

Here’s an example:

from itertools import permutations

def check_perm_pow_oneliner(n, k):
    return any(k ** i == int(''.join(p)) for i in range(int(log(n, k))+2) for p in permutations(str(n)))

n = 521
k = 5
print(check_perm_pow_oneliner(n, k))

Output: True

In a single line, the check_perm_pow_oneliner() function returns True if there is any permutation of n that equals any power of k, using a generator expression within the any function to lazily evaluate permutations against powers of k.

Summary/Discussion

  • Method 1: Brute-force Search. Simple and straightforward. Can be slow for large n.
  • Method 2: Optimized Power Checking. Improves on Method 1 with early exits. Faster than brute-force but still not optimal.
  • Method 3: Using Factorials. Unique approach that avoids permutations. Extremely limited in use due to factorial constraints.
  • Method 4: Mathematical Constraints. Requires less computation by utilizing digit properties and logarithms. Not universally applicable.
  • Method 5: One-Liner with Set Comparison. Elegant and compact. May lack readability and efficiency on its own.