FastPrep

Description

Solutions

Submission

Find Minimum Possible Size

🔥 FULLTIME

Given an array arr of n integers, in a single operation, one can choose two indices, i and j, and delete arr[i] from the array if 2 * arr[i] ≤ arr[j].

A particular element can be chosen at most once. Find the minimum possible size of the array after performing the operation any number of times, possibly zero.

Example 1:

Input:  arr = [1, 2, 3, 4, 16, 32, 64]
Output: 4 
Explanation:
• In the first operation, choose 1 and 16 and delete 1 from the array as 2 * 1 ≤ 16. The array becomes [2, 3, 4, 16, 32, 64].
      
• In the second operation, choose 2 and 32 and delete 2 from the array as 2 * 2 ≤ 32. The array becomes [3, 4, 16, 32, 64].
      
• In the third operation, choose 4 and 64 and delete 4 from the array as 2 * 4 ≤ 64. The array becomes [3, 16, 32, 64].
      
Now the only element that has not been chosen is 3. There have to be two elements, arr[i] and arr[j], for a comparison to take place, so no more operations can occur. The minimum possible size of the array is 4. Note that there are multiple ways to achieve 4 elements in the final array after performing the operations.

Constraints:

N/A