5 Best Ways to Check If Any Permutation of a Large Number is Divisible by 8 in Python

Rate this post

πŸ’‘ Problem Formulation: Given a large number, we want to determine if there exists a permutation of its digits that is divisible by 8. For instance, given the number 123, our Python code should return True, as the permutation 312 is divisible by 8.

Method 1: Brute Force Permutations Check

This method involves generating all permutations of the number’s digits and checking each to see if it’s divisible by 8. The itertools.permutations() function can be used to create a permutations list, and then iterate over each permutation to check for divisibility.

Here’s an example:

from itertools import permutations

def is_divisible_by_8(num):
    for perm in permutations(str(num)):
        if int(''.join(perm)) % 8 == 0:
            return True
    return False

print(is_divisible_by_8(123))

Output: True

This code snippet creates all possible permutations of the digits of the number and checks if any resulting number is divisible by 8. It returns True as soon as it finds one such permutation, which makes it efficient in certain cases.

Method 2: Last Three Digits Check

A number is divisible by 8 if its last three digits form a number that is divisible by 8. This method optimizes the search by only considering permutations of the last three digits and checking for divisibility by 8.

Here’s an example:

def is_divisible_by_8(num):
    num_str = str(num)
    last_digits = num_str[-3:] if len(num_str) >= 3 else num_str
    for perm in permutations(last_digits):
        if int(''.join(perm)) % 8 == 0:
            return True
    return False

print(is_divisible_by_8(123456))

Output: True

This code snippet takes the last three digits of the number and checks all permutations of them for divisibility by 8. This is a more efficient method than brute force permutation check as it greatly reduces the number of permutations to consider.

Method 3: Optimized Divisibility Rules

Using the property that a number is divisible by 8 if and only if its last three digits are, this method further optimizes by checking if any combination of three digits of the number fulfills this condition, avoiding the creation of all permutations.

Here’s an example:

def is_divisible_by_8(num):
    num_str = str(num)
    length = len(num_str)
    for i in range(length):
        for j in range(i+1, length):
            for k in range(j+1, length):
                permutation = num_str[i] + num_str[j] + num_str[k]
                if int(permutation) % 8 == 0:
                    return True
    return False

print(is_divisible_by_8(123456))

Output: True

This code snippet investigates combinations of three digits from the original number by looping through the digits. This avoids generating all permutations and thereby is more efficient but still ensures all combinations are considered.

Method 4: Mathematical Properties

This method uses the mathematical property that a number is divisible by 8 if any three-digit number formed from its digits is divisible by 8. It focuses on creating these numbers in a mathematical way rather than generating permutations.

Here’s an example:

def is_divisible_by_8(num):
    digits = [int(x) for x in str(num)]
    for i in range(0, len(digits) - 2):
        if (digits[i] * 100 + digits[i+1] * 10 + digits[i+2]) % 8 == 0:
            return True
        if (digits[i] * 100 + digits[i+2] * 10 + digits[i+1]) % 8 == 0:
            return True
        if (digits[i+1] * 100 + digits[i] * 10 + digits[i+2]) % 8 == 0:
            return True
        if (digits[i+1] * 100 + digits[i+2] * 10 + digits[i]) % 8 == 0:
            return True
        if (digits[i+2] * 100 + digits[i] * 10 + digits[i+1]) % 8 == 0:
            return True
        if (digits[i+2] * 100 + digits[i+1] * 10 + digits[i]) % 8 == 0:
            return True
    return False

print(is_divisible_by_8(123456))

Output: True

This code snippet forms all different three-digit numbers using mathematical operations and then tests for divisibility by 8. Note that while this method is more efficient than generating permutations, it doesn’t guarantee a consideration of all possible permutations of digits within a large number.

Bonus One-Liner Method 5: Functional Approach

This is a compact one-liner approach using functional programming paradigms such as map and filter to achieve the same result. The expression returns True if any permutation matches the divisibility criteria, all in a single line of code.

Here’s an example:

from itertools import permutations

is_divisible_by_8 = lambda num: any(int(''.join(p)) % 8 == 0 for p in permutations(str(num), 3))

print(is_divisible_by_8(123456))

Output: True

This one-liner uses a lambda function combined with a generator expression to check the divisibility by 8 of any three-digit permutation formed from the number’s digits. It’s a concise method but might not be the most efficient or easily readable.

Summary/Discussion

  • Method 1: Brute Force Permutations Check. Straightforward approach. Can be slow for very large numbers as it generates all permutations.
  • Method 2: Last Three Digits Check. Improved efficiency by reducing the number of checks. May not always find a permutation if fewer than three digits are used.
  • Method 3: Optimized Divisibility Rules. Better performance and ensures all combinations are covered. More complex than previous methods and might still perform unnecessary calculations.
  • Method 4: Mathematical Properties. Makes use of mathematical rules to enhance performance. Does not consider all possible permutations, which might lead to missed solutions.
  • Method 5: Functional Approach. Compact and elegant but potentially less efficient. The succinctness may also impact readability for those not familiar with functional programming.