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