Timeline for HackerRank week of code 32 competition: GeometrickTrick
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 24, 2017 at 8:06 | comment | added | Julien Rousé | Yes I started project euler problems some times ago but often I am really slowed down by my math knowledge and/or algorithmic trick to reduce complexity. | |
| May 24, 2017 at 8:02 | comment | added | ratchet freak | @JulienRousé usually the crucial step for optimizing those kind of problems (like you will notice with project euler problems) is to invert the nested loops using those kind of math tricks to get big O complexity down. | |
| May 24, 2017 at 6:13 | comment | added | Julien Rousé | Thank you a lot for you very good tips and explanation @ratchet, I guess I need to relearn a bit of math to be more able to solve those problems. | |
| May 24, 2017 at 6:09 | vote | accept | Julien Rousé | ||
| May 23, 2017 at 16:18 | comment | added | ratchet freak | @JulienRousé the trick makes sense when you understand how prime factors and multiplication work. Worst case for the inner loop is when i+1 already is a perfect square, then k0 is 1 and the inner loop runs sqrt(i) times. Though most of the time it's less. | |
| May 23, 2017 at 16:05 | comment | added | Julien Rousé |
I can use charAt because String internal is an array right? It's actually a good tip, as I also was wasting lots of memory. Also O(m²) because I square j is a good catch! Totally miss that one. For the algorithm you proposed, your trick for building perfect square out of odd prime factor of another number, is that a known trick? Very cool indeed! Thank you very much, do you think this is the lowest bound for solving this particular problem?
|
|
| May 23, 2017 at 16:01 | history | edited | ratchet freak | CC BY-SA 3.0 |
added 52 characters in body
|
| May 23, 2017 at 15:46 | history | edited | ratchet freak | CC BY-SA 3.0 |
added 514 characters in body
|
| May 23, 2017 at 15:28 | history | answered | ratchet freak | CC BY-SA 3.0 |