The problem statement
This task is a pure precomputation task. Remember how we were finding all prime numbers in O(NlogN) time? Yes, the Sieve of Eratosphen.(If you need info about the sieve of eratosphen go here). We will do the same type of thing here but instead of marking the prime numbers we will mark all the NOT Cube free numbers. Of course the first NOT cube free number is 2*2*2=8 then all the numbers which are divisible on 8 are also NOT cube free so we mark them as well. Then it comes to 3, 3*3*3=27 we mark all the number which are divisibly by 27 , we do this to the number 100 because 100*100*100=10^6 which is the maximum value which can be in teh input. Then we need to numerate all the numbers and the solution is ready. Check the source code for more clarification.
This task is a pure precomputation task. Remember how we were finding all prime numbers in O(NlogN) time? Yes, the Sieve of Eratosphen.(If you need info about the sieve of eratosphen go here). We will do the same type of thing here but instead of marking the prime numbers we will mark all the NOT Cube free numbers. Of course the first NOT cube free number is 2*2*2=8 then all the numbers which are divisible on 8 are also NOT cube free so we mark them as well. Then it comes to 3, 3*3*3=27 we mark all the number which are divisibly by 27 , we do this to the number 100 because 100*100*100=10^6 which is the maximum value which can be in teh input. Then we need to numerate all the numbers and the solution is ready. Check the source code for more clarification.
No comments:
Post a Comment