CODEWITHSUNDEEP
arraysalgorithmmathdata-structures
vkstack
vkstack

Reputation: 1654

Finding largest subset where each number in any pair one number is divisible by the other

Given an array A of size N. I need to find the size of the Largest Subset in which any pair of elements within the subset, one of them is divisible by the other.

In short, find largest subset S, where ∀i,j where i ≠ j and i<|S| and j<|S| either Si%Sj=0 or Sj%Si=0.

The bounds for the problem are:

  1. 1≤ N≤ 10^3
  2. 1≤ Ai≤ 10^9

Sample input/output:

array 4 8 2 3 output is 3

Explanation:

answer set is (4,8,2)

size of the set is 3

Upvotes: 2

Views: 550

Answers (1)

Henry
Henry

Reputation: 43778

I assume there are no duplicates in the array A. One way to do it (pseudocode, assumes array indices starting at 1):

sort the array A to increasing order
allocate an array B the same length as A
for i in 1 .. N do
    B[i] = 1
    for j in 1 .. i-1 do
        if A[i] % A[j] == 0 then
            B[i] = max(B[i], B[j] + 1)
        endif
    endfor
endfor
return the maximum number in array B as answer.

This runs in O(n2) time and uses O(n) extra space. It calculates in array B the length of the longest divisor chain consisting of elements of A and ending at the specific element. The overall maximum in B must be the length of the longest such chain.

Upvotes: 3

Related Questions