Need help with a problem

Revision en1, by Aspergillus, 2024-01-25 18:59:49

This problem has been bugging me since morning today. I have a number K, and an array A with N elements. I can merge any amount of numbers in the array such that each element in the end is at least K. I want to merge minimum number of elements to achieve this, or in other words the final array should have maximum size.

Let's say $$$K = 6$$$ and $$$A = [4, 4, 5, 5, 6, 7, 9]$$$ (here size = $$$N = 7$$$) I have this proposed solution which I have not been able to prove/disprove with several random outputs.

The solution is: consider the subset of A containing all the elements which are less than K, which for this A is $$$A' = [4, 4, 5, 5]$$$, (size = $$$N' = 4$$$), my solution is:

$$$\text{maximum size} = N - N' + \min\left( \frac{N'}{2}, \frac{\sum A'[i]}{K} \right) $$$

For the given example, max length = 3 + min(2, 3) = 5, which corresponds to 9, 9, 6, 7, 9 after merging the 4s and 5s.

If anyone can help me give a counterexample or help me prove the solution, please do so.

Tags help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Aspergillus 2024-01-25 18:59:49 1004 Initial revision (published)