Delete and Conquer

Given an array A of N integers, you are allowed to create a new array B by deleting some (possibly none) elements from array A.

What are the minimum number of elements you have to delete from the A to get B such that every element in B is divisble by every other element in B.

Constraints:

1.   1 <= N <= 100000
2.   1 <= A[i] <= 1000000000

Input:
A single array A.

Output:
Minimum number of elements to delete from A such that every element in the new array is divisble by every other element in the new array

Example:

Input:

A : 10 20 10 20 10 5

Output:

3

Explanation:

The optimal choice is to delete the two 20's and the single 5 so as to get B as :10 10 10.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Delete and Conquer on Interview Code Editor
Sign Up
to access hints and editorial solutions for Delete and Conquer

Discussion


Loading...
Click here to start solving coding interview questions