Wait, you joined this month and you're a 1 kyu already?
I can barely skinny my way through 4kyu python problems...I guess you know maths or algorithms or something?
If n is a power of two this will get trapped in an infinite loop until it exceeds permitted recursion depth.
Because it will reduce down to 1 and the prime test won't catch it.
After seeing the solutions of others, I noticed that their time complexity is O(n**2). I think my solution is O(nlog(n)) since sorting an array takes that time and then a linear scan will check the result.
Here's my brainfuck of a solution. Apparently I wanted to use the Chinese Remainder Theorem for modulo 10 thus giving us a simplified us something easier to compute such as (6a_1 + 5a_2) % 10 where a_1 is the remainder divided by 5 and a_2 is the remainder when divided by 2. The logic is kinda nuts and a lot of repetetive code. I'll improve on this next time.
I have to admit I was sceptical given the clusterfuck this solution was that even I could break it down.
Knowing maths and algorithms probably is not how this person reached 1 kyu.
Wait, you joined this month and you're a 1 kyu already?
I can barely skinny my way through 4kyu python problems...I guess you know maths or algorithms or something?
If n is a power of two this will get trapped in an infinite loop until it exceeds permitted recursion depth.
Because it will reduce down to 1 and the prime test won't catch it.
My solution is longer than most but I think the idea is simply prime factorization.
This is just the travelling salesman problem. An NP-Hard problem with no polynomial time solution.
Probably the fastest and the simplest at the same time!
After seeing the solutions of others, I noticed that their time complexity is O(n**2). I think my solution is O(nlog(n)) since sorting an array takes that time and then a linear scan will check the result.
Here's my brainfuck of a solution. Apparently I wanted to use the Chinese Remainder Theorem for modulo 10 thus giving us a simplified us something easier to compute such as (6a_1 + 5a_2) % 10 where a_1 is the remainder divided by 5 and a_2 is the remainder when divided by 2. The logic is kinda nuts and a lot of repetetive code. I'll improve on this next time.