Question:
During a surge in demand, an electric company activated generators to meet the demand. Now that the demand has passed, at least half of the generators need to be shut down. All generators of a particular model are similar and can be controlled as a single unit. Find the minimum number of models required to deactivate at least half of the generators. If there are n generators, then the ceiling of n/2 generators must be deactivated. The ceiling is obtained when a floating point value is rounded up to the next higher integer. For example, ceiling(5/4)= ceiling(1.25) = 2.
Example: n=14 model = [3, 4, 6, 11, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8].
There are 14 generators, and the ceiling of n/2 = 14/2 = 7. At least 7 generators must be deactivated. One of the optimal solutions is deactivating two types of generators, models 9 and 8. The number of models 9 and 8 is 4 6 = 10, which is >=7. The answer is 2.
Function Description
Complete the function reduceCapacity in the editor below. The function must return an integer.
reduceCapacity has the following parameter(s):
model: an array of integers, the model numbers of each generator.
Constraints
- 1≤n≤10^5
- 1≤model[i]≤10^5
My Code:
public static int reduceCapacity (List<Integer> model) {
HashMap<Integer, Integer> hm=new HashMap<>();
for (int i=0; i<model.size(); i )
{
int digit=model.get(i);
if(hm.containsKey (digit))
{
int count=hm.get(digit);
count =1;
hm.put(digit,count);
}
else
{
int count=1;
hm.put(digit,count);
}
}
double ans=model.size()/2;
int ceil=(int)Math.ceil(ans);
int acval=0;
Set<Integer> keys=hm.keySet();
List<Integer> k=new ArrayList<>();
for (Integer key: hm.keySet())
{
Integer val=hm.get(key);
if(val>1)
{
acval =val;
k.add(key);
}
}
if(ceil>acval)
{
return ceil;
}
else
return k.size();
}
My code didn't pass all the test cases. It was just able to pass 3 test cases. Kindly help me out to come up with an optimal solution for the problem.
CodePudding user response：
TL;DR
The overall approach can be described as follows:
Obtain the number of generators for each model and sort them.
Iterate over the sorted frequencies in descending order (from highest to lowest) tracking the count of models and total number of generators.
Map built-in Sorting
One of the way to address this problem is to create a Map containing frequencies of each model like you've done and then dump its entries into a list and sort them by value (i.e. by frequency).
Then iterate over the list of entries and track the number of models (modelCount in the code shown below) and the total number of generators (numberOfGenerators).
At each iteration step, we need to check if the number of generators exceeded threshold, which according to the description is "ceiling of n/2 generators" (not n/2 like you calculated it in your code). When the threshold is reached, we need to break out of the loop.
Note that you don't need a Set for this problem, since all entries in the Map are guaranteed to have a unique key representing a generator-model.
That's how it might be implemented
public static int reduceCapacity(List<Integer> model) {
Map<Integer, Integer> frequencyByCount = new HashMap<>();
for (Integer next: model) {
frequencyByCount.put(next, frequencyByCount.getOrDefault(next, 0) 1)
}
List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(frequencyByCount.entrySet());
entries.sort(Map.Entry.<Integer, Integer>comparingByValue().reversed());
int threshold = (int) Math.ceil(model.size() / 2.0);
int modelCount = 0;
int numberOfGenerators = 0;
for (Map.Entry<Integer, Integer> entry: entries) {
numberOfGenerators = entry.getValue();
modelCount ;
if (numberOfGenerators >= threshold) break;
}
return modelCount;
}
The time complexity of the solution listed above is O(n log n) due to the usage of built-in quicksort which is used to sort the list of entries.
Arrays Counting Sort
We can also make use of the fact that of values of generator models are reasonably scoped according to the problem constraints [1,100_000]. It would require a bit mo work, but it would allow to improve the time complexity from liner-logarithmic to linear O(n).
We can create an integer array of size 100,000 to calculate the frequencies, basically the first step of the Counting sort algorithm. The next step we have to take to deviate from the Counting sort algorithm (it would come into play a bit later), because we are not interested in sorting actual values of elements. Instead, we need the frequencies to be sorted.
So, we create a list (array would not be handy here since we don't know the size we need) and copy all non-zero frequencies into the list. And now we need to sort it.
And since number models we are given is limited to 100,000 (hence max frequency can't be greater than 100,000) we can utilize Counting sort algorithm, which has a time complexity of O(n).
When we have a sorted array containing numbers of each generator model, the only thing which is left is to iterate over it backwards (from the Highest frequency to the Lowest) and track the count of models and the total number of generators, almost like we've already done.
That's how implementation might look like:
public static int reduceCapacity(List<Integer> model) {
int[] sortedFrequencies = getSortedFrequencies(model);
int threshold = (int) Math.ceil(model.size() / 2.0);
int modelCount = 0;
int numberOfGenerators = 0;
// iterating in Descending order - from the Highest frequency to the Lowest
for (int i = sortedFrequencies.length - 1; i >= 0; i--) {
numberOfGenerators = sortedFrequencies[i];
modelCount ;
if (numberOfGenerators >= threshold) break;
}
return modelCount;
}
public static int[] getSortedFrequencies(List<Integer> list) {
int[] freq = new int[100_000]; // values of `models` are in range [1, 100,000]
for (int next: list) freq[next - 1] ; // calculating frequencies, `index = next - 1` because min value of models is 1 and array indices are zero-based
List<Integer> result = new ArrayList<>();
for (int i = 0, pos = 0; i < freq.length; i ) {
int next = freq[i];
if (next != 0) result.add(next);
}
System.out.println(result);
return countingSort(result);
}
public static int[] countingSort(List<Integer> list) {
int[] freq = new int[100_000]; // values of `frequencies` are in range [1, 100,000]
for (int next: list) freq[next - 1] ; // calculating frequency of each `frequency` (sorry if it sounds confusing)
for (int i = 1; i < freq.length; i ) { // generating cumulative frequency
freq[i] = freq[i - 1];
}
int[] result = new int[list.size()]; // resulting sorted array
for (int i = list.size() - 1; i >= 0; i--) {
int nextItem = list.get(i);
int itemIndex = --freq[nextItem - 1]; // we need to subtract `1` because min value in the `list` would start from `1`, but array indices are zero-based
result[itemIndex] = nextItem;
}
return result;
}