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:
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.