There is a list of numbers of size n, find the maximum count of the number of pairs such that it follows the below pattern:
2 * minimum(arr[i],arr[j]) <= maximum (arr[i], arr[j]), where [i,j] in range (0 to n)The selected indices should be unique, it means if an index say 2 is used to form a pair say (2,5), we should not use the same index 2 to form another pair (2,7).
Example:
arr = [2, 5, 7, 6, 9, 8 , 4 , 2] result = 3Explanation:
Sort input = [2,2,4,5,6,7,8,9]
All possible pairs that can be formed are:
2 can form pairs with [4,5,6,7,8,9]
4 can form pairs with [8,9]
For 5, there is no matching pair that satisfies the condition.We cannot pick the pair (2,4) because if 4 is already used we cannot form new pairs like (4,8) or (4,9)
Finally, we can form 3 maximum counts of pairs using distinct indices, One such possible pairs are (2,5), (7, 2), and (9, 4), so the answer is 3
Example:
arr = [2,1,2,4,1,4,1] result = 3Explanation:
Pairs are (2,1), (4,1), and (2,4), so the answer is 3
Constraints:
- n is in the range 1 to n^5
- each input item,is in range 1 to 10^9
I tried solving this using a TreeMap:
import java.util.*;
public class Main
{
public static void main(String[] args) {
System.out.println(solve(Arrays.asList(2, 5, 7, 6, 9, 8 , 4 , 2)));//3
System.out.println(solve(Arrays.asList(2,1,2,4,1,4,1)));//3
}
static int solve(List<Integer> arr) {
arr.sort(Comparator.reverseOrder());
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int e : arr) map.put(e, map.getOrDefault(e,0)+1);
int result = 0;
for(int e : arr) {
int min = 2 * e;
if(map.get(e) == null) continue;
Integer key = map.ceilingKey(min);
if(key != null) {
map.put(e,map.get(e)-1);
if(map.get(e) <=0)map.remove(e);
map.put(key,map.get(key)-1);
if(map.get(key) <=0)map.remove(key);
result++;
}
}
return result;
}
}
But for 2nd test case arr = [2,1,2,4,1,4,1], I am creating pairs in my code as (2,4), (2,4), so it is returning 2 instead of 3.
I tried greedy and 2 pointer approach but both are not working.
What is the correct approach for this problem?
Based on Matt's answer: Sort and then greedily try to pair right-half elements with left-half elements. O(n log n) for sorting and O(n) for the rest.
static int solve(List<Integer> arr) {
arr.sort(null);
int i = 0, n = arr.size();
for (int j = (n+1)/2; j < n; j++)
if (2 * arr.get(i) <= arr.get(j))
i++;
return i;
}