5 Best Ways to Check if Any Permutation of a Number is Divisible by 3 and is Palindromic in Python

Rate this post

πŸ’‘ Problem Formulation: This article aims to explore the computational strategies to determine if a number has a permutation that is both divisible by 3 and is a palindrome. For example, given the input number ‘312’, one of its permutations ‘132’ is divisible by 3, but not a palindrome. Whereas ‘303’ is a valid permutation that is divisible by 3 and a palindrome. Our goal is to find a method that can verify such conditions effectively in Python.

Method 1: Brute Force Permutations

This method involves generating all possible permutations of the digits in the given number and checking each one for palindromic structure and divisibility by 3. This approach is straightforward but can be quite inefficient for larger numbers due to the factorial growth of possible permutations.

Here’s an example:

from itertools import permutations

def is_divisible_by_3_and_palindromic(num):
    num_str = str(num)
    for perm_tuple in permutations(num_str):
        perm = ''.join(perm_tuple)
        if perm == perm[::-1] and int(perm) % 3 == 0:
            return True
    return False

print(is_divisible_by_3_and_palindromic(312))

Output: True

In the provided code snippet, the function is_divisible_by_3_and_palindromic checks for each permutation (created using Python’s itertools.permutations) if it’s a palindrome and divisible by 3. The function returns True as soon as it finds a valid permutation.

Method 2: Mathematical Checks Before Permuting

To avoid unnecessary permutations, we can apply some mathematical checks. The method checks if the sum of the digits is divisible by 3 and if there are enough digits to form a palindrome. This doesn’t guarantee the existence of a palindromic permutation, but it helps to reduce the search space significantly.

Here’s an example:

from itertools import permutations

def has_palindromic_permutation_divisible_by_3(num):
    num_str = str(num)
    if sum(map(int, num_str)) % 3 != 0:
        return False
    return any(perm == perm[::-1] for perm in set(permutations(num_str)))

print(has_palindromic_permutation_divisible_by_3(312))

Output: True

This function, has_palindromic_permutation_divisible_by_3, first checks if the sum of the digits is divisible by 3 and then creates unique permutations to check for palindromes. This method is more efficient as it removes the need to consider all permutations if the digit sum isn’t divisible by 3.

Method 3: Frequency Map with Early Exit

Building a frequency map of digits reduces the number of permutations we need to check. This is akin to constructing a half-palindrome and ensuring that there’s a combination of the number’s digits that allows the other half to be formed, while also checking the divisibility by 3 of the digits.

Here’s an example:

from collections import Counter

def is_palindrome_div_3(num):
    num_str = str(num)
    if sum(map(int, num_str)) % 3 != 0:
        return False
    freq = Counter(num_str)
    odd_count = sum(1 for val in freq.values() if val % 2 != 0)
    return odd_count <= 1

print(is_palindrome_div_3(312))

Output: True

The is_palindrome_div_3 function creates a frequency count of each digit and then ensures only one or no digits have an odd count, which is a requirement for a number to have a palindromic permutation. It also makes use of the divisibility by 3 rule of the sum of the digits.

Method 4: Optimized Digit Handling

An optimized approach focuses on counting the number of digits and quickly determining potential palindromic outcomes by grouping the digits. This technique avoids full permutation generation and checking, and is more efficient than previous methods.

Here’s an example:

def can_form_palindrome_divisible_by_3(num):
    num_str = str(num)
    digit_count = [0] * 10
    for digit in num_str:
        digit_count[int(digit)] += 1
    odd_count = sum(1 for count in digit_count if count % 2 != 0)
    return odd_count <= 1 and sum(digit_count[i] * i for i in range(10)) % 3 == 0

print(can_form_palindrome_divisible_by_3(312))

Output: True

The function can_form_palindrome_divisible_by_3 checks if there’s at most one digit with an odd count and if the weighted sum of the digits is divisible by 3, thus detecting the possibility of forming a palindromic permutation that’s also divisible by 3 without generating permutations.

Bonus One-Liner Method 5: Functional Approach

For those who appreciate a more functional one-liner, Python’s expressiveness allows us to collapse the logic into a single, albeit complex, expression. This is less readable but showcases Python’s powerful one-liner capabilities.

Here’s an example:

from itertools import permutations

is_palindrome_div_3 = lambda num: any((perm := ''.join(p)) == perm[::-1] and int(perm) % 3 == 0 for p in permutations(str(num)))

print(is_palindrome_div_3(312))

Output: True

This one-liner, assigned to is_palindrome_div_3, uses a generator expression inside Python’s any() function to achieve the same result as previous methods, encapsulating the logic within a lambda function to create a concise but less readable solution.

Summary/Discussion

  • Method 1: Brute Force Permutations. Easy to understand. Inefficient for large numbers due to factorial time complexity.
  • Method 2: Mathematical Checks Before Permuting. More efficient by avoiding some permutations. Still not optimal for large numbers.
  • Method 3: Frequency Map with Early Exit. Much more efficient by focusing on digit counts. Applicable for numbers of reasonable length.
  • Method 4: Optimized Digit Handling. Highly efficient by avoiding permutations altogether. Best for performance on larger numbers.
  • Method 5: Functional Approach. Showcases Python’s expressiveness. Not user-friendly for understanding or debugging.