1
$\begingroup$

So the problem states:

An array of $N (1 \leq N \leq 2000)$ natural numbers is given. Find the cardinality of the largest subset of that array such that for every two numbers $A$ and $B$ either $A|B$ or $B|A$ (or both).

I know you don't like it when people post questions without trying anything, but the only thing I can possibly think of (that would work) is brute force, which would mean exploring every possible subset and then checking the given condition, again, by brute force.

But since the time complexity of subset exploration is $O(2^N)$, and $N = 2000$ in the worst case, this solution becomes pretty useless.

Other thing I had in mind was some kind of divide and conquer algorithm, similar to merge-sort. But I can't think of a way I'd use the results of two (left and right) subarrays to compute the result for their union.

So, any ideas?

Thanks.

EDIT: The brute force solution I've made that seems to be working (C++):

int largestSubset(const vector<int>&arr, int i, vector<int>&subset, int j){
    if(i == arr.size()){
        //brute force check
        for(int k = 0; k < j; k++){
            for(int s = k + 1; s < j; s++){
                if ((subset[k] % subset[s] != 0) && (subset[s] % subset[k] != 0)){
                    return 0;
                }
            }
        }
        return j;
    }

    //skip the i-th element
    int count1 = largestSubset(arr, i+1, subset, j);
    //include the i-th element
    subset[j] = arr[i];
    int count2 = largestSubset(arr, i+1, subset, j+1);


    return  max(count1, count2);

}
$\endgroup$
  • $\begingroup$ try brute force solutions for a small number of N (< 25) - maybe it will give some insight. $\endgroup$ – knok16 Aug 27 at 13:26
  • 1
    $\begingroup$ I've added the brute-force solution to the question. It seems to work. Still no insight, though. $\endgroup$ – Koy Aug 27 at 13:45
2
$\begingroup$

You can do it in $O(N^2)$ like that:

First, sort your array $L$ in increasing order.

Then, for $i \in \{0,\ldots,N-1\}$, let $M[i]$ denote the cardinality of the largest valid subset $S$ such that $L[i]$ is the largest element of $S$.

We can compute $M[i]$ in a dynamic programming fashion: $$ M[0] = 1$$ $$\forall i \;\; s.t.\;\; 0<i<N-1: M[i] = 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$$ (where the max is taken to be equal to $0$ if no $L[j]$ divides $L[i]$)

To see that, notice that it is clear that $M[i] \leq 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$ as the second largest element in the corresponding subset must divide $L[i]$. Moreover, the fact that the second largest element $L[j]$ divides $L[i]$ and that the subset without $L[i]$ is valid is enough to guarantee that the subset with $L[i]$ is valid, as all elements in the subset are compatible between them and all divide $L[j]$ and thus divide $L[i]$. Thus the dynamic programming formulation is correct.

Then, the value you are looking for is simply the maximum over all $M[i]$'s.

This leads directly to a $O(N^2)$ algorithm as the sorting can be done in $O(N\log(N))$, and finding the maximum in $M$ is done in $O(N)$.

$\endgroup$
  • $\begingroup$ Pretty nice solution. Just tried it, works fine. On a side note, this problem came up within a course in which dynamic programming is not taught (it was taught in the course just before this one). So it kind of forces me to think that there may be some other solution as well, not involving DP. I was thinking segment trees because that's one of the subjects covered by this course (apart from graph algorithms and geometric algorithms which wouldn't be of much use here). If you have any thoughts on a possible segment-tree solution or something similar I'd be glad to hear. Thanks anyway. $\endgroup$ – Koy Aug 27 at 14:12
  • $\begingroup$ Did the course include stuff about DAGs and topological sorting? Because this problem can also be rephrased as finding the longest path in a certain DAG, where there is an edge u-->v if u divides v. (But that's really the same thing as what I wrote if you think about it) $\endgroup$ – Tassle Aug 27 at 14:57
  • $\begingroup$ Yeah, the course does include topsort and DAGs. Nice insight. I'll try and solve it using graphs as well. Thanks again. $\endgroup$ – Koy Aug 27 at 15:04
  • $\begingroup$ A very very nice and simple solution. I wonder how hard it would be to make it faster than O (n^2) - for example, if you have a billion 64 bit integers, the solution won't have more than 64 elements, so we would hope it can be found faster than in a billion squared operations. $\endgroup$ – gnasher729 Aug 27 at 19:24
  • $\begingroup$ You're right. You made me think about it a bit more and I found a quite straightforward $O(N \log(N)\log(M_{max}))$ solution where $M_{max}$ is the maximum value in $M$. This can be further reduced to $O(N\log(N) + N\log(M_{max}))$ by using a hashmap with $O(1)$ inserts and lookup. Not sure if I should include it as an edit to this answer or give another one? $\endgroup$ – Tassle Aug 27 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.