# [Community Puzzle] Nuggets numbers

https://www.codingame.com/training/hard/nuggets-numbers

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 ?

Memoization is the key, take a look at this technique.

@Oioi, @Djoums.
Iâ€™m having problems with valitator 7, what should i review?

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