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}
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 than 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.
Below is the implementation of the above approach:
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 << "\n" ; cout << "Total Pairs = " << count << "\n" ; } // 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 |
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 , "\n" ; echo "Total Pairs = " , $count , "\n" ; } // 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 ?> |
Javascript
<script> // Javascript 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 var smallest = 1000000000; var count=0; // iterate over all pairs for ( var i=0; i<n; i++) for ( var j=i+1; j<n; j++) { // is Math.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 Math.abs value is equal to smallest // increment count value else if (Math.abs(arr[i] + arr[j] - k) == smallest) count++; } // print result document.write( "Minimal Value = " + smallest + "<br>" ); document.write( "Total Pairs = " + count + "<br>" ); } // driver program var arr = [3, 5, 7, 5, 1, 9, 9]; var k = 12; var n = arr.length; pairs(arr, n, k); </script> |
Minimal Value = 0 Total Pairs = 4
Time Complexity: O(n2) where n is the number of elements in the array.
Auxiliary Space : O(1)
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 << "\n" ; cout << "Total Pairs = " << count << "\n" ; } // 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; } |
Python3
# Python program to find number of pairs # and minimal possible value from sys import maxsize from bisect import bisect_left, bisect_right # function for finding pairs and min value def pairs(arr, n, k): # initialize smallest and count smallest = maxsize count = 0 s = set () # iterate over all pairs s.add(arr[ 0 ]) for i in range ( 1 , n): # Find the closest elements to k - arr[i] sorted_s = sorted (s) index = bisect_left(sorted_s, k - arr[i]) if index = = len (sorted_s): lower = sorted_s[index - 1 ] else : lower = sorted_s[index] index = bisect_right(sorted_s, k - arr[i]) if index = = len (sorted_s): upper = sorted_s[index - 1 ] else : upper = sorted_s[index] # Find absolute value of the pairs formed # with closest greater and smaller elements. 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 elif curr_min = = smallest: count + = 1 s.add(arr[i]) # print result print ( "Minimal Value = " , smallest) print ( "Total Pairs = " , count) # driver program arr = [ 3 , 5 , 7 , 5 , 1 , 9 , 9 ] k = 12 n = len (arr) pairs(arr, n, k) # This code is contributed by vikramshirsath177. |
Java
import java.util.*; class Main { // function for finding pairs and min value static void pairs( final int [] arr, final int n, final int k) { // initialize smallest and count int smallest = Integer.MAX_VALUE, count = 0 ; Set<Integer> s = new TreeSet<>(); // iterate over all pairs s.add(arr[ 0 ]); for ( int i = 1 ; i < n; i++) { // Find the closest elements to k - arr[i] int lower = Integer.MIN_VALUE; int upper = Integer.MAX_VALUE; for (Integer x : s) { if (x <= (k - arr[i]) && x >= lower) { lower = x; } if (x >= (k - arr[i]) && x <= upper) { upper = x; } } // Find absolute value of the pairs formed // with closest greater and smaller elements. int curr_min = Math.min(Math.abs(lower + arr[i] - k), Math.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.add(arr[i]); } // print result System.out.println( "Minimal Value = " + smallest); System.out.println( "Total Pairs = " + count); } // driver program 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); } } |
Javascript
function pairs(arr, n, k) { // initialize smallest and count let smallest = Number.MAX_SAFE_INTEGER; let count = 0; let s = new Set(); // iterate over all pairs s.add(arr[0]); for (let i = 1; i < n; i++) { // Find the closest elements to k - arr[i] let lower = [...s].find((element) => element >= k - arr[i]); let upper = [...s].find((element) => element >= k - arr[i]); // Find absolute value of the pairs formed // with closest greater and smaller elements. let curr_min = Math.min(Math.abs(lower + arr[i] - k), Math.abs(upper + arr[i] - k)); // if 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.add(arr[i]); } // print result console.log(`Minimal Value = ${smallest}`); console.log(`Total Pairs = ${count}`); } // driver program let arr = [3, 5, 7, 5, 1, 9, 9]; let k = 12; let n = arr.length; pairs(arr, n, k); |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // function for finding pairs and min value static void pairs( int [] arr, int n, int k) { // initialize smallest and count int smallest = int .MaxValue, count = 0; SortedSet< int > s = new SortedSet< int >(); // iterate over all pairs s.Add(arr[0]); for ( int i = 1; i < n; i++) { // Find the closest elements to k - arr[i] int lower = s.Where(e => e >= k - arr[i]).DefaultIfEmpty( int .MinValue).First(); int upper = s.Where(e => e > k - arr[i]).DefaultIfEmpty( int .MaxValue).First(); // Find absolute value of the pairs formed // with closest greater and smaller elements. int curr_min = Math.Min(Math.Abs(lower + arr[i] - k), Math.Abs(upper + arr[i] - k)); // if 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.Add(arr[i]); } // print result Console.WriteLine( "Minimal Value = " + smallest); Console.WriteLine( "Total Pairs = " + count); } // driver program 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); } } |
Minimal Value = 0 Total Pairs = 4
Time Complexity : O(n Log n)
Auxiliary Space: O(n)
Contact Us