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.
Project Euler #95: Amicable chains
Project Euler #95: Amicable chains
Sort by
recency
|
7 Discussions
|
Please Login in order to post a comment
you can find my java solution here
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 .
Small hint if you're still struggling with time constaints, the result doesn't change for N>1E6.
Stacktrace:
Native stacktrace:
Debug info from gdb:
Could not attach to process. If your uid matches the uid of the target process, check the setting of /proc/sys/kernel/yama/ptrace_scope, or try again as the root user. For more details, see /etc/sysctl.d/10-ptrace.conf ptrace: Operation not permitted. No threads.
================================================================= Got a SIGSEGV while executing native code. This usually indicates a fatal error in the mono runtime or one of the native libraries
used by your application.
thi is what i got...
Is there a time constraint for problems like these, my code takes more than 30 seconds for n = 16000 , PS. Im new to hackerrank contests