[Community Puzzle] Regular polygons

https://www.codingame.com/training/medium/regular-polygons

Send your feedback or ask for help here!

Created by @Witman,validated by @nicola1,@Master_Zain and @Razovsky.
If you have any issues, feel free to ping them.

Nice puzzle, when b gets big, I get a time exceeded msg. No idea how to optimize !

We can think about eliminate power 2 elements using this form of div 2:
j>>=(int)(log2(j & -j));
as this will avoid one loop, it will help to resolve medium range test but not the last test.

try to make a library of distinct products of fermat prime numbers and then use it to count its multiply in provided range. (think out of the box)
vector dist_Fermat_primes={1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765};

The powers of 2 are solutions to the problem, so I already did that. It’s the last test that I can not pass !!

I already did that. I think the problem is in the way i loop over each number between a and b !!

After 3 days of thinking about the problem, I finally got all the tests working…
My initial mistake was that although I read up about Fermat Primes (and that there are only 5 of them) I had the feeling that hard-coding them in my solution is somehow cheating :stuck_out_tongue: So I tried checking numbers to see if they are Fermat primes. And although I did everything to avoid checking the same number twice it was still pretty slow.
Hardcoding the 5 Fermat primes in a Set and checking for every number between a and b whether it is divisible only by those 5 numbers and 2, got me through the medium test, but it was still awfully slow for the long range.
And as you suggest, the problem is looping through everything in between a and b. So my last version (and this one passes all the tests), constructs all the possible 31 product of Fermat primes and saves them in a Set (plus the number 1) and then I just go over each of them and keep them multiplying by 2 as long as the product is less than b. So instead of checking numbers, I actually just generate the correct ones.

2 Likes

Yes, that is what I mean, instead of checking, create all multiplies of fermat primes in provided range and then just count what was created, congratulation THaruca.

Now I see what you meant omarekik. That worked, thank you :slight_smile:
But what if the last condition b<2^31 was to change? Can we calculate the product of Fermat’s primes dynamically? hmmm

I pass test 1,2 ,3 and 4, but not the last test.
I find 483 instead of 494.
Anybody who can help?