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.
Very easy after all the training from previous problems. At the beginning, generate a list of all sums of factors in a manner similar to how we use Sieve of Eratosthenes. You may refer to Problem 21 which is related to amicable numbers.
Then use a queue to trace the chain for every iteration, and only update the answer if an occurrence of the first element in the chain is found (though you would still have to break the chain if there is any repeating element, otherwise it will never quit). You may refer to Problem 74 which is related to measuring the length of a chain.
Note that every member in the same chain has the same length, so once you are done with the smallest member, you won't have to care about the rest. As a result, you should store the intermediate elements you've gone through so you don't have to do the same thing again, as they are definitely not a smallest element in the chain, or you would have seen them before (because you've finished every candidate smaller than it before this iteration step).
And, you may have noticed, that not every number can form a chain in this case. For example, when you hit a prime number, it goes to and stops at .
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #95: Amicable chains
You are viewing a single comment's thread. Return to all comments →
Very easy after all the training from previous problems. At the beginning, generate a list of all sums of factors in a manner similar to how we use Sieve of Eratosthenes. You may refer to Problem 21 which is related to amicable numbers.
Then use a queue to trace the chain for every iteration, and only update the answer if an occurrence of the first element in the chain is found (though you would still have to break the chain if there is any repeating element, otherwise it will never quit). You may refer to Problem 74 which is related to measuring the length of a chain.
Note that every member in the same chain has the same length, so once you are done with the smallest member, you won't have to care about the rest. As a result, you should store the intermediate elements you've gone through so you don't have to do the same thing again, as they are definitely not a smallest element in the chain, or you would have seen them before (because you've finished every candidate smaller than it before this iteration step).
And, you may have noticed, that not every number can form a chain in this case. For example, when you hit a prime number, it goes to and stops at .