Given an array of integers and number K, write a program to find the number of pairs which has sum equal to K.

**Example:**

int input [] = {6, 3, 2, 9, 2, 2, 2, 1} int K = 4 Output: 7 int input [] = {5, 5, 5, 5} int K = 10 Output: 6 int input [] = {1, 2, 3, 4} int K = 5 Output: 2

**Naive Approach:**

Use nested loops and compare each element with all other elements and check if the difference to elements is K, if yes then count it.

Time Complexity:** O(N ^{2})**

**Better Solution: Sorting.**

- Sort the array
in ascending order.*input[]* - Initialize
.*pairs = 0* - Have two pointers, let’s call these
and*i*.*j*at index 0 and*i*at index input.length-1.*j* - Check
- If input[i] + input[j] > K then do
.*j–* - If input[i] + input[j] < K then do
.*i++* - If input[i] + input[j] = K, then count all the occurrences of input[i] (say
) and input[j] (say*x*), then*y*. If input[i] and input[j] are same then*pairs += x*y*and*n = x + y*.*pairs += n*(n+1)/2*

- If input[i] + input[j] > K then do

Time Complexity: **O(nlogn)**

**Complete Code:**

**Output**

Number of pairs with sum = 4 is/are: 7