×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

Two elements whose sum is closest to zero

C++ implementation to find two elements whose sum is closest to zero.
Submitted by Vikneshwar GK, on January 20, 2022

Consider an array of size n and it contains both positive and negative elements. For example, if n=5, the array elements can be like -5, 5, 0, 2, -1. The task at hand is to find any two elements from the array whose sum is closest to zero.

Example:

Input:
test1[] = {-4, 2, 6, 5, -7, -1, 9, -8}

Output:
2 and -1

Explanation:
The sum of 2 and -1 is 1 which is closest to 0 
than the sum of any other element. 
Pairs like (5,-4), (9, -8) are also correct answers 
as their sum is also equal to 1 but since the question 
asks for any 2 pairs, we are going with 2 and -1.

Input:
test1[] = {-3, 10, 8, -2, 2, -1}

Output:
-2 and 2

Explanation:
Sum of -2 and 2 is 0.

Solution 1: Compare all elements

This is a usual approach to solve this problem, i.e., finding the sum of every element with every other element and output the one that is closest to zero.

C++ Implementation:

#include <bits/stdc++.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

// Function to find elements whose sum
// is closest to zero
void closestToZero(int array[], int length)
{
    int sum_min, sum, left_min, right_min;

    // array length check
    // must contain atleast two elements
    if (length < 2) {
        cout << "Invalid Input";
        return;
    }

    // initialize variablees
    left_min = 0;
    right_min = 1;
    sum_min = array[0] + array[1];

    // nested loop to iterate through the array
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            sum = array[i] + array[j];

            // finding minimum sum
            if (abs(sum_min) > abs(sum)) {
                sum_min = sum;
                left_min = i;
                right_min = j;
            }
        }
    }

    // print the elements
    cout << "Sum closest to zero elements : " << array[left_min] << " and " << array[right_min];
}

int main()
{
    int array[100], N;

    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    closestToZero(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1:-3
Enter element 2:10
Enter element 3:8
Enter element 4:-2
Enter element 5:2
Enter element 6:1
Sum closest to zero elements : -2 and 2

Time Complexity: O(n2)

Solution 2: Sorting the array

This approach involves sorting the array using an O(nlog(n)). Then use two pointers to point the start and end of the array. It involves the following steps:

  • Step 1: start=0 and end=length-1
  • Step 2: find sum which is the sum of array elements at start and end position
  • Step 3: if sum is negative, then increment starts
  • Step 4: if sum is positive, then decrement end
  • Step 5: Check for minimum sum at every step
  • Step 6: Repeat step 2 to step 5 until start >= end

C++ Implementation:

#include <bits/stdc++.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

// Function to find elements whose sum
// is closest to zero
void closestToZero(int array[], int length)
{
    // Initialize variables
    int sum = 0, sum_min = INT_MAX, start = 0, end = length - 1, start_min = 0, end_min = length - 1;

    // array length check
    // must contain atleast two elements
    if (length < 2) {
        cout << "Invalid Input";
        return;
    }

    // sort the elements
    sort(array, array + length);

    while (start < end) {
        sum = array[start] + array[end];

        // finding minimum sum
        if (abs(sum) < abs(sum_min)) {
            sum_min = sum;
            start_min = start;
            end_min = end;
        }
        if (sum < 0)
            start++;
        else
            end--;
    }

    cout << "Sum closest to zero elements: "
         << array[start_min] << " and " << array[end_min];
}

int main()
{
    int array[100], N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    closestToZero(array, N);

    return 0;
}

Output:

Enter Number of elements: 8
Enter element 1:-4
Enter element 2:2
Enter element 3:6
Enter element 4:5
Enter element 5:-7
Enter element 6:-1
Enter element 7:9
Enter element 8:-8
Sum closest to zero elements: -8 and 9

Time Complexity: O(nlog(n))

This approach involves sorting whose time complexity is O(nlog(n)) and although it finds minimum sum with time complexity of O(n), the overall time complexity remains O(nlog(n)).


Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.