Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
There are several ways to solving this kata, micro optimisation is not required.
This comment is hidden because it contains spoiler information about the solution
I created a Python solution that passes
10^12tests but always gets timeout in10^18tests. The step 1 of the solution is prime factorization form. Step 1 is just 1/10 lines of code in the entire solution, however, step 1 takes the majority of the running time because prime factorization is a known hard problem and it is the basis of RSA encryption.In my solution, the prime factorization is
O(sqrt(m))time complexity. So for10^18tests, it's a10^9loop, which is close to Python language's capacity.Prime factorization seems a neccesary step to me. I think the only way to pass the kata is to optimize the prime factorization step. However, it might not be possible in a slow language like Python. Even if optimization is possible, it might be overcomplicated for a 3 kyu problem.