2
\$\begingroup\$

I was solving Project Euler Problem #52:

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.

in C++, and this is the code I used:

#include <algorithm>
#include <iostream>
#include <string>

bool checkCondition(long long int number);

int main()
{
    long long int num = 1;
    while (!checkCondition(num))
    {
        ++num;
    }

    std::cout << num << "\n";
}

bool checkCondition(long long int number)
{
    std::string numString = std::to_string(number);
    std::string numx2 = std::to_string(number * 2);
    std::string numx3 = std::to_string(number * 3);
    std::string numx4 = std::to_string(number * 4);
    std::string numx5 = std::to_string(number * 5);
    std::string numx6 = std::to_string(number * 6);

    return std::is_permutation(numString.begin(), numString.end(), numx2.begin()) &&
        std::is_permutation(numString.begin(), numString.end(), numx3.begin()) &&
        std::is_permutation(numString.begin(), numString.end(), numx4.begin()) &&
        std::is_permutation(numString.begin(), numString.end(), numx5.begin()) &&
        std::is_permutation(numString.begin(), numString.end(), numx6.begin());
}

As evident, this function uses the standard library function std::is_permutation and literally iterates over every single integer and converts them to strings to find the answer, which is obviously inefficient. How can I improve upon the efficiency of this program?

\$\endgroup\$
4
  • \$\begingroup\$ Don't convert to string. And use maths. \$\endgroup\$ Jun 13, 2018 at 12:33
  • \$\begingroup\$ In theory, you could convert numx2 (and, btw, use arrays, not numbered variables) to a string, test it, and move on if it fails. You don't have to convert all the numbers to strings and then check them. You could also sort the letters of the string and then compare for equality, but std::is_permutation may already do that. \$\endgroup\$
    – user1149
    Jun 13, 2018 at 17:06
  • \$\begingroup\$ Check out codeproject.com/Articles/1244739/… Rather than checking for permutation, I generate permutations. \$\endgroup\$
    – JDługosz
    Jun 14, 2018 at 0:58
  • \$\begingroup\$ Converting to string (lots of modulo-10) is very slow. An approach that starts with loose digits and multiplies out to make a computational number would be better in that respect. \$\endgroup\$
    – JDługosz
    Jun 14, 2018 at 1:02

2 Answers 2

4
\$\begingroup\$

Before I begin: I solved this particular Project Euler problem in 10 seconds without even writing a program, because I had seen a Numberphile video on this concept and I had memorized the number. It's really just a mathematical problem!

Whenever you must do brute force, you have two primary goals:

  1. Reduce the number of trials by eliminating some definitely incorrect cases. In this example, if N and N * 6 doesn't have the same number of digits, they cannot be the permutations of each other. In our case this won't be much useful, but if you did some maths, you would notice that you would only have to check numbers between 100000..~170000, 200000..~270000, because numbers outside those ranges don't satisfy the condition stated above. If we were asked to find a much larger solution, using this approach would have eliminated about 30% of the options right away.

  2. Reduce the amount of effort you must give at each trial. In this case, if 2 * N isn't a permutation of N, you shouldn't check for 3 * N because you know that you aren't getting a solution.

Finally, if I were you, I wouldn't use string operations. You can convert each number into a sorted list of digits in it, and then check for list equality.

Combining all of the above, you could write something like this:

A = sorted list of digits in (current trial)
for i = 2 to 6 inclusive:
    B = sorted list of digits in (current trial times i)
    if A and B are different, fail
succeed! -- can only reach here if all former multiples are permutations
\$\endgroup\$
2
\$\begingroup\$

Haskell is particularly good at this kind of problems. I hope this gives you some inspiration to do it in a imperative language.

Note that comparison of strings having the same digits is easy. You only have to check that they have the same length and are the same string when they are ordered.

-- euler 52
-- smallest x, such that 2x, 3x, 4x, 5x, and 6x contains the same digits as x

import Data.List

-- check if all string in the list are a permutation of characters
hasSameDigits :: Show a => [a] -> Bool
hasSameDigits []  = True
hasSameDigits [_] = True
hasSameDigits (a:b:xs) = compare (show a) (show b) && hasSameDigits xs
    -- compare two lists having some permutation of characters
    where compare x y = length x == length y && sort x == sort y

-- the list of all xs starting at 10^(n-1) such as the list of multiplications 
-- of this number to n have a permutation of the same digits
candidatesList :: (Integral a, Show a) => a -> [a]
candidatesList n = [x | x <- [10^(n-1)..] , hasSameDigits $ map ((*) x) [1..n] ]

solution :: Integer
solution = head $ candidatesList 6

{-
OUTPUTS
*Main> solution
142857
-}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.