Given an array of only positive integers you have to delete the minimum number of elements from the array to make the array a good sequence.
A good sequence is where all the occurrence of elements is divisible by a common positive integer that is GREATER THAN 1.
E.g (2,2,3,3,3,3) is a good sequence because the occurrence of every element is divisible by 2. (There are 2 instances of 2 and 4 instances of 3)
E.g (1,1,4,4,4) is not a good sequence because the occurrence of every element is not divisible by any positive integer.
Sample inputs/outputs:
[6,1,1,7,6,3,6,6,5] --> output: 3 (Remove the single instance of 7, 5 and 3 and therefore the remaining occurrences is all divisible by 2 because we will be left with 4 instances of 6 and 2 instances of 1. Left with [1,1,6,6,6,6])
[5,2] --> output: 2 (Removing both numbers because none can be divisible by smallest positive integer which is 2. Left with [])
[7,5,7,3,4,7,4,6,7,7,3,2,1] --> output: 5 (remove the single instance of 1, single instance of 2, single instance of 5, single instance of 6 and one instance of 7 and now all the occurrences will be divisible by 2. Left with [7,7,7,7,4,4,3,3])
Wanted to share this question and to find more optimal solutions. So please share your solution and time and space complexities
MY SOLUTION (DO NOT READ IF YOU WANT TO SOLVE IT YOURSELF)
import java.util.*;
public class MyClass {
public static void main(String []args){
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(6,1,1,7,6,3,6,6,5)))); // 3
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(3,6,5,1,5,1,3,4,3,4,4,7,1,1)))); // 4
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(1,4,3,1,3,2,5,1,2,4,6,3,2))));// 4
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(7,3,5,3)))); // 2
System.out.println();
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(2,1,3,5,2,3,5,5,6,7,4,5,6,7,6)))); // 3
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(5,7,1,3,5)))); // 3
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(5,2)))); // 2
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(2,2,6,6,1,6,7,2,7,4,1,2,7)))); //3
System.out.println();
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(1,5,3,3,3,5,3,1,7,3,4,5,6,3,5)))); // 3
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(3,3,6,7,3,1,4,7)))); // 4
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(2,2,4,3,6,4,4,1,7,4,3,2,6,2,1,7,5,5,5,5)))); // 0
System.out.println();
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(7,5,7,3,4,7,4,6,7,7,3,2,1)))); // 5
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(3,3,7,7,6,4)))); // 2
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(4,4,4,7,3,1,2,4,7,1,3,2,7,3,5,6,5,4,5,4)))); // 4
System.out.println(solution(new ArrayList<Integer>(Arrays.asList(7,2,6,7,2,5,6,5,7,3,1,3,4,5,5,3,7,6,7)))); // 5
}
public static Integer solution(List<Integer> array) {
// Time O(k*n) | Space O(n) where n is the size of the input array and k is the maximum frequency of a number in that array. Worse case k = 10^3 because that is the constraint
Map<Integer, Integer> map = new HashMap<>();
int maxValue = Integer.MIN_VALUE;
for(Integer x : array) {
map.merge(x, 1, Integer::sum);
if(x > maxValue)
maxValue = x;
}
Collection<Integer> frequencies = map.values();
int minimumDeletions = Integer.MAX_VALUE;
for(int i = 2; i <= maxValue; i++) {
int currentMinDeletions = 0;
for(Integer value : frequencies) {
if(value % i == 0) continue;
if(value < i)
currentMinDeletions += value;
else
currentMinDeletions += value % i;
}
minimumDeletions = Math.min(currentMinDeletions, minimumDeletions);
}
return minimumDeletions == Integer.MAX_VALUE ? 0 : minimumDeletions;
}
}