Deshaw coding question

help
1

Two arrays A and P are given where a have N elements and P have M elements.All the elements of P are prime.There is some change you can make on A .You can pick any element Ai (where 0<= i < N) and increase or decrease it by 1.

Now you need to calculate the minimum number of times you need to increase or decrease the elements of A so that every element of A is divisible by at least one element of array P.

Constraints:

  • 1 <= N,M <= 1000000
  • 1<= Ai<= 1000000
  • 1<= Pi<= 1000000

Please can anyone tell the method to solve the problem optimally.

1 Like
2

What was the time limit, I have a bruteforce solution in mind with possibly O(n^2) time complexity, Array size was really 10^6?

3

Use sieve to find all the numbers that are divisible by the elements in P. (Put them in a vector/array) say V.
Sort the vector V.
For each element A[i] find the next nearest element in the vector V ( left and right) using binary search ( lower_bound and upper_bound). Take the nearer of those two to A[i]. The difference will give the min moves for A[i] to become divisible by atleast one of P[i].

Add for all A[i]. That will be the answer.

6 Likes
4

Will it work ?
Suppose array of primes is {2,7,13,19}
And one of the value in array A is 15 then answer should be 1 instead of 2.
Because 14 is divisible by 7.

1 Like
5

Precompute all prime factors of all numbers in range 1 to 10^6 (using sieve of eratosthenes).
Now for start removing prime factors which are not given in array P (use map/set maybe).
Now make an array having value 0 if none of the factor left with that value (after removing). And 1 if at least one factor left.
Now compute prefix sum of that array.
Now use binary search ( upper/lower bound) for computing answer.

1 Like
6

I said find all the numbers which will be divisible by the prime numbers list.
So 14 will be there in that list (because of 2). And you will get ans as 1.

8

This is not what your are saying :thinking:

9

How can you do that with binary search without adding modifications which I did ? :thinking:
PS : your solution will give 13.

10

I have edited my earlier comment. Please read again

11

The answer is 0 ,because 15 is divisble by 5. @l_returns

12

My bad remove 5. \hspace{1mm}

13

Still same question. How will it find 14 ?
Nearest element in vector V is 13 and not 7.

14

I think we have to compute all numbers which are divisible by atleast one of the primes in the array. Then we need to find the closest element for each number in A.

15

because 14 is in the list . he stored all the elements of p and there all multiples in common array so 13 and 14 both are in a list.

16

Yup that is what I said already.

17

Sorry. Correct. \hspace{1mm}

1 Like
18

how to generate all numbers divisible by the primes in p.

19

only store multiples of Pā€™s elements in a set and then use binary search

20

For(i=p;i<=n;i+=p) \hspace{1mm}

21

Ok ,Thanks for the Idea