CODEWITHSUNDEEP
javaarraysalgorithm
intvprep
intvprep

Reputation: 71

Largest divisible subset in array

Given an array the task is to find the largest divisible subset in array. A subset is called divisible if for every pair (x, y) in subset, either x divides y or y divides x.

Example

Input : arr[] = {1, 16, 7, 8, 4} Output : 16 8 4 1 In the output subset, for every pair, either the first element divides second or second divides first.

Input : arr[] = {2, 4, 3, 8} Output : 8 4 2

Here is what I have come up with. The time complexity is O(n^2). can it be improved ? 

public static int[] largestDivisibleSubset2(int[] a){

    Arrays.sort(a);
    int index=0;
    int maxDivCount=0;
    for(int i=0;i<a.length;i++){
        int currentDivCount=0;
        for (int j=i;j<a.length;j++ ) {
            if(a[j]%a[i]==0){
                currentDivCount++;
            }
        }
        if(currentDivCount>maxDivCount){
            index = i;
            maxDivCount = currentDivCount;
        }
        currentDivCount = 0;
    }
    int[] res = new int[maxDivCount];
    int k=0;
    for(int i=0;i<a.length;i++){
        if(a[i]%a[index]==0){
            res[k++] = a[i];            
        }
    }

    return res;
}

Upvotes: 4

Views: 1739

Answers (1)

sprinter
sprinter

Reputation: 27996

On modern multi-core machines (and the much improved facilities for use of them in Java 8) it is often easier to look for ways to use all cores before optimising sequential processing times. This is especially true if reducing time complexity will also reduce readability or maintainability.

For example, here's a solution to your problem that uses parallel streams in Java 8 while deciding whether to add a value to a subset. On my own ancient machine it can find the largest divisible subset of 50,000 random integers in 14 secs (22 seconds if I remove the parallel method). There are clearly optimisations possible but, unless there's a specific reason, choose clarity first. Especially in interviews :-)

public int[] getSubSet(int... set) {
    int[] largest = new int[0];
    for (int value : set) {
        int[] subset = Arrays.stream(set).parallel()
                .filter(n -> n % value == 0 || value % n == 0).toArray();
        if (subset.length > largest.length)
            largest = subset;
    }
    return largest;
}

Upvotes: 2

Related Questions