[5 Aug 2020]Two elements whose sum is closest to zero

 

Question: An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.

For the below array, program should print -80 and 85.


# include <bits/stdc++.h>
# include <stdlib.h> /* for abs() */
# include <math.h>
  
using namespace std;
void minAbsSumPair(int arr[], int arr_size)
{
    int inv_count = 0;
    int l, r, min_sum, sum, min_l, min_r;
      
    /* Array should have at least
       two elements*/
    if(arr_size < 2)
    {
        cout << "Invalid Input";
        return;
    }
      
    /* Initialization of values */
    min_l = 0;
    min_r = 1;
    min_sum = arr[0] + arr[1];
      
    for(l = 0; l < arr_size - 1; l++)
    {
        for(r = l + 1; r < arr_size; r++)
        {
        sum = arr[l] + arr[r];
        if(abs(min_sum) > abs(sum))
        {
            min_sum = sum;
            min_l = l;
            min_r = r;
        }
        }
    }
      
    cout << "The two elements whose sum is minimum are "
         << arr[min_l] << " and " << arr[min_r];
}
  
// Driver Code
int main()
{
    int arr[] = {1, 60, -10, 70, -80, 85};
    minAbsSumPair(arr, 6);
    return 0;
}
  
The two elements whose sum is minimum are -80 and 85

Time complexity: O(n^2)

Algorithm
1) Sort all the elements of the input array using their absolute values.
2) Check absolute sum of arr[i-1] and arr[i] if their absolute sum is less than min update min with their absolute value.
3) Use two variables to store the index of the elements.

Implementation

// C++ implementation using STL
#include <bits/stdc++.h>
using namespace std;
  
// Modified to sort by abolute values
bool compare(int x, int y)
{
    return abs(x) < abs(y);
}
  
void findMinSum(int arr[], int n)
{
    sort(arr, arr + n, compare);
    int min = INT_MAX, x, y;
    for (int i = 1; i < n; i++) {
  
        // Absolute value shows how close it is to zero
        if (abs(arr[i - 1] + arr[i]) <= min) {
  
            // if found an even close value
            // update min and store the index
            min = abs(arr[i - 1] + arr[i]);
            x = i - 1;
            y = i;
        }
    }
    cout << "The two elements whose sum is minimum are "
         << arr[x] << " and " << arr[y];
}
  
// Driver code
int main()
{
  
    int arr[] = { 1, 60, -10, 70, -80, 85 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findMinSum(arr, n);
    return 0;
    // This code is contributed by ceeyesharish
}


Output:

The two elements whose sum is minimum are -80 and 85


Time Complexity: O(nlogn)
Space Complexity: O(1)




































Comments

Post a Comment

Popular posts from this blog

[13 Feb 2020] Check if a given sequence of moves for a robot is circular or not

Check if a given sequence of moves for a robot is circular or not Link:  https://www.youtube.com/watch?v=f7Zd8hEbCz0 Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following. G - Go one unit L - Turn left R - Turn right Input: path[] = "GLGLGLG" Output: Given sequence of moves is circular Input: path[] = "GLLG" Output: Given sequence of moves is circular The idea is to consider the starting position as (0, 0) and direction as East (We can pick any values for these). If after the given sequence of moves, we come back to (0, 0), then given sequence is circular, otherwise not. N | | W -------------- E | | S The move ‘G’ changes either x or y according to following rules. a) If current direction is North, then ‘G’ increments y and doesn’t cha...
Read more

Typical Programs in C/C++

  Sum of two large numbers Difficulty Level :   Medium   Last Updated :  04 Jun, 2019 Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers. Examples: Input : str1 = "3333311111111111", str2 = "44422222221111" Output : 3377733333332222 Input : str1 = "7777555511111111", str2 = "3332222221111" Output : 7780887733332222 The idea is based on school mathematics. We traverse both strings from end, one by one add digits and keep track of carry. To simplify the process, we do following: 1) Reverse both strings. 2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10. 3) Finally reverse the result. // C++ program to find sum of two large numbers. #include<bits/stdc++.h> using namespace std;     // Function for finding sum of la...
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more