In an array — 'arr' there are n elements. Two elements arr[i] and arr[j] can be combined to one element if arr[i] >= k * arr[j], for i != j. After combination, these two elements cannot further combine with any other element of the array. Find the minimum size of the array possible, after executing atmost n/2 operations.
Input will be n, the array elements and k.
Please share source/link to the problem statement.
When the order of the elements does not matter (as in the problem you described), it is generally a good idea to sort the array and assume the elements in order when coming up with a solution.
This said, each match decreases the size of the array by one, therefore the final size will be $$$n - matches$$$. If the final size has to be minimal, you want to maximize the numbers of matches.
Time complexity is $$$O(n\log n)$$$. If the time limit is very tight, in practice you can achieve $$$O(n)$$$ using radix sort and two pointers.