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}
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 :
- abs( ai + aj – K) > smallest : do nothing as this pair will not count in minimal possible value.
- abs(ai + aj – K) = smallest : increment the count of pair resulting minimal possible value.
- 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<bits/stdc++.h> 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<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 ( 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 else if (abs(arr[i] + arr[j] - k) == smallest) count++; } // print result cout << "Minimal Value = " << smallest << "
"; cout << "Total Pairs = " << count << "
"; } // driver program int main() { int arr[] = {3, 5, 7, 5, 1, 9, 9}; int k = 12; int n = sizeof(arr) / sizeof(arr[0]); pairs(arr, n, k); return 0; } |
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<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 System.out.println("Minimal Value = " + smallest); System.out.println("Total Pairs = " + count); } /* Driver program to test above function */ public static void main(String[] args) { 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 Arnav Kr. Mandal. |
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
<?php // PHP program to find number of // pairs and minimal possible value // function for finding pairs // and min value function pairs($arr, $n, $k) { // initialize smallest and count $smallest = PHP_INT_MAX; $count = 0; // iterate over all pairs for ($i = 0; $i < $n; $i++) for($j = $i + 1; $j < $n; $j++) { // 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 else if (abs($arr[$i] + $arr[$j] - $k) == $smallest) $count++; } // print result echo "Minimal Value = " , $smallest , "
"; echo "Total Pairs = ", $count , "
"; } // Driver Code $arr = array (3, 5, 7, 5, 1, 9, 9); $k = 12; $n = sizeof($arr); pairs($arr, $n, $k); // This code is contributed by aj_36 ?> |
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<bits/stdc++.h> 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<n; i++) { // Find the closest elements to k - arr[i] int lower = *lower_bound(s.begin(), s.end(), k - arr[i]); int upper = *upper_bound(s.begin(), s.end(), k - arr[i]); // Find absolute value of the pairs formed // with closest greater and smaller elements. int curr_min = min(abs(lower + arr[i] - k), abs(upper + arr[i] - k)); // is abs value is smaller than smallest // update smallest and reset count to 1 if (curr_min < smallest) { smallest = curr_min; count = 1; } // if abs value is equal to smallest // increment count value else if (curr_min == smallest ) count++; s.insert(arr[i]); } // print result cout << "Minimal Value = " << smallest <<"
"; cout << "Total Pairs = " << count <<"
"; } // driver program int main() { int arr[] = {3, 5, 7, 5, 1, 9, 9}; int k = 12; int n = sizeof(arr) / sizeof(arr[0]); pairs(arr, n, k); return 0; } |
Output:
Minimal Value = 0 Total Pairs = 4
Time Complexity : O(n Log n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments