Is the p here is every prime in the array.
1 Like
Use set to avoid repetition. As he said.
I think you know that.
Then what will be the time complexity
O(10^6*log(10^6)) \hspace{1mm}
I think it would be O (n root n ) time complexity.
I don’t think so. \hspace{0mm}
Take an integer array of size 1000000 having initial value as -1, let it be “sieve”
sort array P.
Iterate through P and mark multiples of P with value as P. By this, we have all those numbers which are be divisible by at least one of the elements of array P.
Now, iterate through values of A. if value of sieve[A[i]] is -1, then we need to increment or decrement. Get the minimum increments or decrements. This is one way to do it.
Another way is, Instead of maintaining sieve array, push all divisible numbers into set and use set.find() to get if present number is divisible. If not, find minimum of difference of immediate greater and least number.
1 Like
Can you explain how do you get that log n factor?
I think, factors, always deal with O(root n )complexity.
You should check sieve of eratosthenes.
Google it.
Yeah. I messed up, I thought it takes O( root n). Thanks.
https://code.hackerearth.com/c8128dt
Here is a code .I have done stress testing too and it executes within 1 sec on codechef compiler.
could u please ideone the code, code.hackerearth isn’t working