Determine the number of pairs of elements in a given array that sum to a value smaller than the given target number.

Assumptions

• The given array is not null and has length of at least 2

Examples

• A = {1, 2, 2, 4, 7}, target = 7, number of pairs is 6({1,2}, {1, 2}, {1, 4}, {2, 2}, {2, 4}, {2, 4})

  public int smallerPairs(int[] array, int target) {
    Arrays.sort(array);
    int i = 0, j = array.length - 1, count = 0;
    while (i < j) {
      int sum = array[i] + array[j];
      if (sum < target) {
        count += j - i;
        i++;
      } else {
        j--;
      }
    }
    return count;
  }