Reputation: 71
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
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