# Count number of pairs in an array with sum = K

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(N2)

Better Solution: Sorting.

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

Time Complexity: O(nlogn)

Complete Code:

Output

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