https://www.codingame.com/training/hard/nuggets-numbers
Send your feedback or ask for help here!
Created by @Thib34,validated by @Oioi,@Djoums and @UncleV.
If you have any issues, feel free to ping them.
1 Like
Should be moved to easy?
2 Likes
It was medium when I approved it, which was fine imo.
Nice it is became best
1 Like
Tho I could write a 6 lines solution in Python, it requires DP or memoization and good understanding of gcd’s properties so it’s eather a hard Medium or an easy Hard.
@pardouin: My guess is that you missed the easy (and probably more efficient) way to solve this puzzle. 
In my opinion, putting back this puzzle in medium would give players a hint about the existence of a trick.
I checked your haskell solution and you use gcd and memoization so I don’t see how it contradicts what I was saying.
1 Like
Easy or medium. LOL… I’ve got to be stupid since I’m struggling since 2 days on it. Read a lot of math algorithm but couldn’t find a solutio. Oh yeah, I’ve one but for last steps it’s too time consuming.
So I’m stuck. Somebody can help ?
I’m on the same boat. I have time issues only on the last test. I’m missing a trick I guess.
Nice puzzle, and I agree for placement in the Hard section. My brain is in fire !
Just one sad thing, 8/8 on the tests cases, but only 6/8 for the validators 
Strange, and it will be hard to find out what’s wrong 
@Thib34 is it possible to take a look to the validators 5 and 7 ?
Here is validator 7
Input
15
411
366
138
930
648
969
318
189
756
414
195
360
417
573
675
Output
-1
Edit : it was the wrong one
You are wrong, it’s not validator 7, it’s the 8th test.
Validator 7
15
411
366
138
930
648
969
318
189
756
414
195
360
417
573
675
Output
-1
1 Like
There is a O(1) solution for the case n=2,
I’m studying for find also the O(1) solution for the case n=3, (of course not useful for this puzzle, since it is not enough, but just for math curiosity), it seems to me that it should exists.
I have already an “almost working” formula 
, any math nerd that wants struggle on it?
1 Like
No need for maths here. I built the sieve like a horse race.
I’m having trouble with Validator 8. Any hints would be appreciated.
You should ensure the sieve is large enough, and at the same time not too large to cause timeout.
@nicola do you have a suggestion how to dynamically find a suitable max size of the sieve to use?
No, I used a magic number here. 
Now I know I’m not the only one playing magic in this solution.
1 Like