Pairing numbers (a,b) in an array such a way that a*2 >=b

  • A+
Category:Languages

I am trying to solve pairing numbers (a,b) in an array such a way that a*2 >=b. Where a and b are numbers from input array.

Examples:

input: a[] = {1,2,3,4,5}

output: 2

explanation:

  • we can pair 1 with 3
  • 2 with 4 or 5

input: a[] = {4,3,2,1,5}

output: 2

explanation:

  • we can pair 1 with 3
  • 2 with 4 or 5

input: a[] = {4,3,2,1,5,6}

output: 3

explanation:

  • we can pair 5 with 1
  • 2 with 4
  • 3 with 6

I tried to solve the problem using recursion like below, but this does not give any right results. Any help would be appreciated.

  • Sort the input array
  • if a[start] * 2 >= [end] found then add 1 to result recur for start +1 and end - 1
  • else recur for (start + 1, end), (start, end - 1) and (start + 1, end - 1)

Idea is matching a[start] with remaining elements in the array and get max result.

    public static int countPairs(int[] a){        Arrays.sort(a);        return countPairs(a,a.length,0,a.length-1);     }      public static int countPairs(int[] a, int n, int start, int end){           if(end == start){             return 0;         }         if(start >= n || end < 0){             return 0;         }           System.out.print("matching start: "+start + " and end "+end+"   ");System.out.println("matching "+a[start] + " and "+a[end]);          if(a[start] < a[end] && a[start] * 2 >= a[end]  ){              int res = countPairs(a,n,start+1,end-1) +1;              //System.out.print("inside if matching start: "+start + " and end "+end+"   ");System.out.println("matching "+a[start] + " and "+a[end] + " count is "+res);             return res;         }         else{              return max(countPairs(a,n,start+1,end) ,                     countPairs(a,n,start,end - 1),countPairs(a,n,start+1,end - 1));         }      } 

tests:

import org.junit.Test;  import java.util.Arrays; import java.util.Random;   public class CountingPairsTest {      static int countPairs(int[] a){         return PairingNumbers.countPairs(a);     }      @Test      public void test1(){         int[] a = {1,2,3,4,5};         System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     }      @Test public void test2(){         int[] a = {1,2,3,4,5,6};         System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     }      @Test public void test5(){         int[] a = {1,2,3,7,4,5,6};         System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     }      @Test public void test6(){         int[] a = {9,8,20,15,21};          System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     }      @Test public  void test3(){         int[] a = {5,4,3,2,1};         System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     }      @Test public void test4(){         int[] a = {2,4,5,3,1};          System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     }      @Test public void test7(){         int[] a = new Random().ints(10,1,100).toArray();// IntStream.range(1,100).toArray();           System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     }     @Test public void test8(){         int[] a = new Random().ints(10,1,10).toArray();// IntStream.range(1,100).toArray();           System.out.println("****************************************/n" + Arrays.toString(a));         int count = countPairs(a);         System.out.println("count "+count);     } } 

 


I suggest that the answer is a.length / 2. Half of the length of the array (rounded down if the length was odd). You can pair the numbers any way you like. For non-negative a and b if a * 2 < b, just swap a and b and you will have a * 2 >= b. So since it takes two numbers to make a pair, you can always form precisely as many pairs as half of the length of the array.

Example (from the comments): [1, 2, 2, 2]. Length is 4, half of the length is 2, so there should be 2 pairs. Let’s check: (1, 2) is a nice pair because 1 * 2 >= 2. (2, 2) is another nice pair since 2 * 2 >= 2. In this case we didn’t even need any swapping (on the other hand the same pairs would have worked with swapping too: 2 * 2 >= 1 and 2 * 2 >= 2).

It will not always work if the array may contain negative numbers. So you may want to add a validation of the array that checks that it doesn’t.

What went wrong in your solution?

Your recursive algorithm is wrong. Say the array is [2, 3, 7, 9]. Clearly (2, 3) and (7, 9) are nice pairs, so there are two pairs here. The way you describe your algorithm, since (2, 9) is not a valid pair, you discard at least one of 2 and 9, leaving no chance of forming two pairs from the remaining numbers.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: