We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Given the constraint k<10^100 a O(n) algorithm is not a viable solution, no matter the optimizations.
Another idea is to check all the unique combinations (combinations with repetitions) of digits, and then add the permutations of that number to the total if found to be a perfect square (and less than k).
Es. 3 digits: 001, 010 and 100 are the same, and so are 123, 132, 213, 231, 312, 321. With checking one of them you know all the others, whether they are a perfect square or not.
But, brute-force searching to all the possible unique combinations for 100 digits would have a cost of:
(10 + 100 - 1)! / (100! * (10-1)!) ~ 10^12, less than 10^100, but still not at all feasible.
EDIT: Nevermind, forgot the cost of the permutations.
EDIT2: Even without the cost of the permutations, just looping through all the possibile digits alternatives and checking if one is a perfect square or not, I got timeout for 15/19 of the test cases.
There must be some way to know those square numbers, or the correct guess of the sum, in advance.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #171: Finding numbers for which the sum of the squares of the digits is a square
You are viewing a single comment's thread. Return to all comments →
Given the constraint k<10^100 a O(n) algorithm is not a viable solution, no matter the optimizations.
Another idea is to check all the unique combinations (combinations with repetitions) of digits, and then add the permutations of that number to the total if found to be a perfect square (and less than k).
Es. 3 digits: 001, 010 and 100 are the same, and so are 123, 132, 213, 231, 312, 321. With checking one of them you know all the others, whether they are a perfect square or not.
But, brute-force searching to all the possible unique combinations for 100 digits would have a cost of: (10 + 100 - 1)! / (100! * (10-1)!) ~ 10^12, less than 10^100, but still not at all feasible.
EDIT: Nevermind, forgot the cost of the permutations.
EDIT2: Even without the cost of the permutations, just looping through all the possibile digits alternatives and checking if one is a perfect square or not, I got timeout for 15/19 of the test cases.
There must be some way to know those square numbers, or the correct guess of the sum, in advance.