Tutorialspoint.dev

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 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<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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter