# Minimum Possible value of |ai + aj – k| for given array and k.

You are given an array of n integer and an integer K. Find the number of total unordered pairs {i, j} such that absolute value of (ai + aj – K), i.e., |ai + aj – k| is minimal possible where i != j.

Examples:

```Input : arr[] = {0, 4, 6, 2, 4},
K = 7
Output : Minimal Value = 1
Total  Pairs = 5
Explanation : Pairs resulting minimal value are :
{a1, a3}, {a2, a4}, {a2, a5}, {a3, a4}, {a4, a5}

Input : arr[] = {4, 6, 2, 4}  , K = 9
Output : Minimal Value = 1
Total Pairs = 4
Explanation : Pairs resulting minimal value are :
{a1, a2}, {a1, a4}, {a2, a3}, {a2, a4}

```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple solution is iterate over all possible pairs and for each pair we will check whether the value of (ai + aj – K) is smaller then our current smallest value of not. So as per result of above condition we have total of three cases :

1. abs( ai + aj – K) > smallest : do nothing as this pair will not count in minimal possible value.
2. abs(ai + aj – K) = smallest : increment the count of pair resulting minimal possible value.
3. abs( ai + aj – K) < smallest : update the smallest value and set count to 1.

## C++

 `// CPP program to find number of pairs  and minimal  ` `// possible value ` `#include ` `using` `namespace` `std; ` ` `  `// function for finding pairs and min value ` `void` `pairs(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// initialize smallest and count ` `    ``int` `smallest = INT_MAX; ` `    ``int` `count=0; ` ` `  `    ``// iterate over all pairs ` `    ``for` `(``int` `i=0; i

## Java

 `// Java program to find number of pairs  ` `// and minimal possible value ` `import` `java.util.*; ` ` `  `class` `GFG { ` `     `  `    ``// function for finding pairs and min value ` `    ``static` `void` `pairs(``int` `arr[], ``int` `n, ``int` `k) ` `    ``{ ` `        ``// initialize smallest and count ` `        ``int` `smallest = Integer.MAX_VALUE; ` `        ``int` `count=``0``; ` `      `  `        ``// iterate over all pairs ` `        ``for` `(``int` `i=``0``; i

## Python3

# Python3 program to find number of pairs
# and minimal possible value

# function for finding pairs and min value
def pairs(arr, n, k):

# initialize smallest and count
smallest = 999999999999
count = 0

# iterate over all pairs
for i in range(n):
for j in range(i + 1, n):

# is abs value is smaller than smallest
# update smallest and reset count to 1
if abs(arr[i] + arr[j] – k) < smallest: smallest = abs(arr[i] + arr[j] - k) count = 1 # if abs value is equal to smallest # increment count value elif abs(arr[i] + arr[j] - k) == smallest: count += 1 # print result print("Minimal Value = ", smallest) print("Total Pairs = ", count) # Driver Code if __name__ == '__main__': arr = [3, 5, 7, 5, 1, 9, 9] k = 12 n = len(arr) pairs(arr, n, k) # This code is contributed by PranchalK [tabby title="C#"]

 `// C# program to find number  ` `// of pairs and minimal  ` `// possible value ` `using` `System; ` ` `  `class` `GFG  ` `{ ` ` `  `// function for finding ` `// pairs and min value ` `static` `void` `pairs(``int` `[]arr,  ` `                  ``int` `n, ``int` `k) ` `{ ` `    ``// initialize  ` `    ``// smallest and count ` `    ``int` `smallest = 0; ` `    ``int` `count = 0; ` ` `  `    ``// iterate over all pairs ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``for``(``int` `j = i + 1; j < n; j++) ` `        ``{ ` `            ``// is abs value is smaller  ` `            ``// than smallest update  ` `            ``// smallest and reset  ` `            ``// count to 1 ` `            ``if` `(Math.Abs(arr[i] +  ` `                ``arr[j] - k) < smallest ) ` `            ``{  ` `                ``smallest = Math.Abs(arr[i] +  ` `                                    ``arr[j] - k); ` `                ``count = 1; ` `            ``} ` ` `  `            ``// if abs value is equal  ` `            ``// to smallest increment ` `            ``// count value ` `            ``else` `if` `(Math.Abs(arr[i] + ` `                              ``arr[j] - k) ==  ` `                                ``smallest) ` `                ``count++; ` `        ``} ` ` `  `    ``// print result ` `    ``Console.WriteLine(``"Minimal Value = "` `+  ` `                                ``smallest); ` `    ``Console.WriteLine(``"Total Pairs = "` `+ ` `                                 ``count);  ` `} ` ` `  `// Driver Code ` `public` `static` `void` `Main()  ` `{ ` `    ``int` `[]arr = {3, 5, 7,  ` `                 ``5, 1, 9, 9}; ` `    ``int` `k = 12; ` `    ``int` `n = arr.Length; ` `    ``pairs(arr, n, k); ` `} ` `} ` ` `  `// This code is contributed ` `// by anuj_67. `

## PHP

 ` `

Output:

```Minimal Value = 0
Total Pairs = 4
```

An efficient solution is to use a self balancing binary search tree (which is implemented in set in C++ and TreeSet in Java). We can find closest element in O(log n) time in map.

## C++

 `// C++ program to find number of pairs ` `// and minimal possible value ` `#include ` `using` `namespace` `std; ` ` `  `// function for finding pairs and min value ` `void` `pairs(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// initialize smallest and count ` `    ``int` `smallest = INT_MAX, count = 0; ` `    ``set<``int``> s; ` ` `  `    ``// iterate over all pairs ` `    ``s.insert(arr[0]); ` `    ``for` `(``int` `i=1; i

Output:

```Minimal Value = 0
Total Pairs = 4
```

Time Complexity : O(n Log n)