Project Euler Problem 52 Solution: Permuted Multiples

Project Euler Problem 52 Statement

It can be seen that the number, $125874$, and its double, $251748$, contain exactly the same digits, but in a different order.

Find the smallest positive integer, $x$, such that $2x$, $3x$, $4x$, $5x$, and $6x$, contain the same digits.

Solution

The HackerRank version extends the original Project Euler problem by requiring us to find all numbers within a given constraint space where a number and its multiples (from $2x$ to $Kx$) are permutations of each other. To solve this, we employ a straightforward brute-force approach to systematically query each candidate.

Optimization with Divisibility by 9: We can safely start our search with $125874$ (as shown in the HackerRank problem statement) which is a multiple of $9$ and increment by $9$ for each query. Numbers that are permutations of each other always share the same digital root, which implies they are divisible by $9$.

Using the "splat" (unpacking argument lists), *, operator we can print on one line the contents of the dynamicly created list through the range of the k results:

print(*[m*i for m in range(1, K+1)])

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 52

HackerRank Project Euler 52: Given $N$, find all the positive integers, $x\le N$, such that $x, 2x, \dots, Kx$ contain the same digits.

Python Source Code

N,K = map(int, input().split())
is_perm = lambda i,j:sorted(str(i))==sorted(str(j))
q = range(2, K+1)

for i in range(125874, N+1, 9):
    if all(is_perm(i, m*i) for m in q):
        print(*[m*i for m in range(1, K+1)])

Last Word

Project Euler 52 code:

print (next(i for i in range(10, 1000000) if all(sorted(str(i)) == sorted(str(i*j)) for j in range(2, 7))))