How do I solve this Array question of Sorting Positive and negative digits in C++?

Arcshahi 0
Viewed 43

An array of length L is given. Elements are '–ve' and +ve integers. Make a function that figure out all positive numbers in the array that have their opposites in it as well.

Input : 4,5,8,3,2,-5,-8,-4,-2,-3,-5,8,-8

Output : 2,-2,3,-3,4,-4,5,-5,8,-8

I copied this code from the web but couldn't understand it, is there some other easier way.

#include <bits/stdc++.h>
using namespace std;
 

void printPairs(int arr[], int n)
{
    vector<int> v;
 
    
    for (int i = 0; i < n; i++)
 
        
        for (int j = i + 1; j < n; j++)
 
            // If absolute values are equal print pair.
            if (abs(arr[i]) == abs(arr[j]))
                v.push_back(abs(arr[i]));
 
    if (v.size() == 0)
        return;
 
   
    for (int i = 0; i < v.size(); i++)
        cout << -v[i] << " " << v[i] << " ";
}
 

int main()
{
    int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    
    printPairs(arr, n);
    return 0;
}
sorting arrays c++
2 Answers

I think the algorithm is not correct, just looking at absolute values. Also it is quadratic O(n²), 1,000 items would need 500,000 steps.

Sort the array. -8, -5, -4, 2, 4, 8, 9

Now you can have two iterators, from the beginning (-8) for negative numbers and from the end (9) for positive numbers.

As long the iterators are in the negative resp. positive range, you can advance to absolutely identical numbers. Mind repeats ..., 13, 13, 13, ....

The coding I leave to you. Would not like to spoil it.

Joop Eggen0

Using standard algorithms does not always immediately make code easier, but standard algorithms are well documented. If you do not understand application of a standard algorithm you can find plenty of documentation. That isnt the case for self-written algorithms.

Know your algorithms! I will use a simpler example: 2,1,-2,2, and I will use a std::vector.

  • std::sort can be used to sort the vector to 1,2,2,-2 by using a custom comparator that compares the elements absolute values and places positive elements before negative ones ( to achive that you can compare std::pairs of {abs(element),element<0}).
  • std::unique can be used to move adjacent duplciates to the end of the vector, resulting in 1,2,-2,2. The returned iterator refers to the 2 because thats the end of the vector that has only the unique elements. (Here it is not actually needed to erase the duplicates from the vector)
  • std::adjacent_find can be used to find pairs of adjacent elements for which abs(a) == abs(b).

Thats all you need.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int main() {
    std::vector<int> x{4,5,8,3,2,-5,-8,-4,-2,-3,-5,8,-8};

    std::sort(x.begin(),x.end(),[](auto a,auto b){ return std::make_pair(std::abs(a),a<0) < std::make_pair(std::abs(b),b<0);});
    
    auto last = std::unique(x.begin(), x.end());
    //x.erase(last, x.end()); // no need to actually erase

    auto it = x.begin();
    while (it != last) {
        it = std::adjacent_find(it,last,[](auto a,auto b){ return std::abs(a) == std::abs(b);});
        if (it != last) { 
            std::cout << *it << " " << *std::next(it) << "\n"; 
            it += 2;    
        }
    }
}

I am not expecting that you find this code much simpler to read compared to the original, but if you just spend some time on the documentation of the used algorithms it should become clear how it works.

463035818_is_not_a_number0
Related