Find the largest number (in a range) that has each digit exactly once and is divisible by 11

user_15444015 0
Viewed 244

I was given a task to find the largest number between 1023456789 and 9876543210 that contains all numbers between 0 and 9 exactly once and that can be divided by 11. I wrote a bit of code that technically should have been able to find this number through brute force (Keep in mind this Python 3.6). The code is as follows:

print(max(x for x in range(1023456789, 9876543210) if x % 11 == 0 and '0' in str(x) and '1' in str(x) and '2' in str(x) and '3' in str(x) and '4' in str(x) and '5' in str(x) and '6' in str(x) and '7' in str(x) and '8' in str(x) and '9' in str(x)))

I apologize if the code looks weird as I am still inexperienced. When I tried it with the minimum value, it took about two hours for me to get the result. In this case, the computer was still looking after eight hours. In hindsight, it is logical, it was bound to happen, so now I am looking for an alternative approach to accelerate this process and get my result sooner if possible.

python
4 Answers

The question involves a simple permutation of a 10 digit number consisting one of 0-9, so this could be generated using itertools.permutations, using a string containing all those digits arranged in highest to lowest order

Given the nature of the permutation algorithm is that the output will be "emitted in lexicographic ordering according to the order of the input iterable", thus it would guarantee that the numbers produced will be in the correct decreasing order, starting from the biggest (the initial input). This would then allow the naive solution where simply iterating through that generator and cast the resulting list of characters into a string then into an int, then do the modulus will eventually get to the desired output.

import itertools
  
def solution():
    for raw in itertools.permutations('9876543210'):
        number = int(''.join(raw))
        if number % 11 == 0:
            return number

print(solution())

This prints out 9876524130 as the solution after 51 iterations.

For completeness, in the spirit of the original one-liner:

>>> next(n for n in (int(''.join(raw)) for raw in itertools.permutations('9876543210')) if n % 11 == 0)
9876524130
user_29048960

Here is a way to do it more efficiently:

  1. Start to calculate the biggest modulo 11 number in the range: it will be the start of the for loop, this avoids the max function call later.

  2. Do a for loop starting from the biggest and decrease by -11 steps. This reduce the numbers to test, avoids the modulo testing for each one, and avoids calling the max function later.

  3. Convert the number to a string and put the digits/letters in a set. This is an easy way to check you have all the 10 different digits.

  4. If the set has exactly 10 elements, you get the right number. break as you do not need to spend time with other numbers.

The code will be:

biggestm11 = (9876543210 // 11) * 11

for x in range(biggestm11, 1023456789-1, -11):
    num = set(str(x))
    if len(num) == 10:
        print(x)
        break

Output:

9876524130
user_146621790

A short comparison between the suggested solutions here.

The results are:

using_set took 0.1783951

using_iter took 0.0033607000000000498

[other two are still running...]

Code to reproduce:

import timeit

def using_set():
    biggestm11 = (9876543210 // 11) * 11

    for x in range(biggestm11, 1023456789 - 1, -11):
        num = set(str(x))
        if len(num) == 10:
            return x

def using_iter():
    import itertools

    for raw in itertools.permutations('9876543210'):
        number = int(''.join(raw))
        if number % 11 == 0:
            return number

def using_max():
    return max(x for x in range(1023456789, 9876543210) if
              x % 11 == 0 and '0' in str(x) and '1' in str(x) and '2' in str(x) and '3' in str(x) and '4' in str(
                  x) and '5' in str(x) and '6' in str(x) and '7' in str(x) and '8' in str(x) and '9' in str(x))


def using_short_max():
    numbers = []
    for x in range(9012345678, 9876543210):
        if x % 11 == 0:
            if '0' in str(x) and '1' in str(x) and '2' in str(x) \
                    and '3' in str(x) and '4' in str(x) and '5' in str(x) \
                    and '6' in str(x) and '7' in str(x) and '8' in str(x) \
                    and '9' in str(x):
                numbers.append(x)

    return max(numbers)

funcs = [using_set, using_iter, using_short_max, using_max]
for func in funcs:
    print(func.__name__, "took", timeit.timeit(f"__main__.{func.__name__}()", "import __main__", number=100))
user_60458000

I think people have given awesome efficient answers, but I worked with your code to use your method and logic to accelerate the time as you requested. Since the number is 10 digits long, we can safely assume that it will be between 9012345678 and 9876543210 (since we want the leading digit to be 9 to get the biggest number). This reduces the range a lot.

%%time
numbers = []
for x in range(9012345678, 9876543210):
    if x % 11 == 0:
        if '0' in str(x) and '1' in str(x) and '2' in str(x) \
        and '3' in str(x) and '4' in str(x) and '5' in str(x) \
        and '6' in str(x) and '7' in str(x) and '8' in str(x) \
        and '9' in str(x):
            numbers.append(x)

I appended all possibilities to a list to find the maximum of the list and got 9876524130 which is the correct answer. It took my laptop under 2 minutes and my laptop is not powerful at all.

user_121557120
Related