I am trying to solve the following problem using C++

Question

The objective is to return all pairs of integers from a given array of integers that have a difference of 2. The result array should be sorted in ascending order of values. Assume there are no duplicate integers in the array. The order of the integers in the input array should not matter.

My code here:

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

std::vector<std::pair<int, int>> twos_difference(const std::vector<int> &vec) {
  vector <int> v1 = vec;
  vector <pair<int,int>> pairs;
  sort(v1.begin(),v1.end(), greater<int>());
  
  for (size_t i=0; i<vec.size()-1; i++){
    pair <int,int> due;
    for (size_t j=1; j<vec.size(); j++){
      if (v1[i] - v1[j] == 2){
        due.first = v1[j];
        due.second = v1[i];
        pairs.push_back(due);
        break;
      }
      
    }
  }
    

  sort(pairs.begin(),pairs.end());

  return pairs;""
}

Execution Timed Out (12000 ms) WHY??????

your solution is `O(n^2)`. There is a solution that's `O(n log n)`. Think about a different algorithm to solve this problem. — bolov, Dec 10 '21 at 22:54
why do you check all pairs of elements (after you sorted the input vector) ? How far can be two elements be apart when their difference is 2 ? Anyhow, "Execution Timed Out" seems to be from some online judge. Why? Because your code takes too much time i guess — 463035818_is_not_an_ai, Dec 10 '21 at 22:55
The obligatory: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h — Passerby, Dec 10 '21 at 22:56
You almost have it. Sort the items ascending not descending and then make the inner loop iterate starting at the index of the outer loop until the difference is greater than 2 and then break out of the inner loop, emplace a pair that was exactly of difference two if there was one. You need to decide whether you are outputing multiple copies of the same pairs that are separated by two if there are more than one, or if you just want unique pairs. — jwezorek, Dec 10 '21 at 23:51
Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. — Community, Dec 17 '21 at 08:01

score 0 · Answer 1 · answered Dec 15 '21 at 12:50

We are here to help.

I analysed the code and checked, what could be the issue here.

From this, you can derive measures for improvements.

Please check the below list, maybe this gives you and idea for further development.

You pass the input vector by reference, but then copy all the data. No need to do. Use the given input vector as is. Except, of course, if the source data is still neded
You define your resulting std::vector "pairs" but do not reserve memory for this. Using push_back on this std::vector will do a lot of memory reallocation and copying. Please use std::pairs.reserve(vec.size()/2);after the definition of "pairs".
No need to handover "greater" to the sort function. The sort function will do that by default
Double nested loops are not needed. Your values are already sorted. You can use a single loop and then compare vec[i] with [vec[i+1]. This will reduce the complexity from quadratic to linear.
At the end, you sort again the pairs. This is not necessary, as the values were already sorted before
Please compile with all optimizations on, like "Release Mode" or "-O3"

See the below example which creates fist 10.000.000 random and unique test values and then measures the execution of the operation for finding the required pairs.

Execution time is below 1 second on my machine.

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

#include <random>
#include <unordered_set>
#include <limits>
#include <chrono>
#include <fstream>


constexpr size_t MaxValues = 10'000'000;
std::vector<int> createTestValues() {
    std::random_device rd;      // Will be used to obtain a seed for the random number engine
    std::mt19937 gen(rd());     // Standard mersenne_twister_engine seeded with rd()
    std::uniform_int_distribution<> distrib(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());

    std::unordered_set<int> values{};
    while (values.size() < MaxValues)
        values.insert(distrib(gen));
    return { values.begin(), values.end() };
}

int main() {
    std::vector values = createTestValues();

    auto start = std::chrono::system_clock::now();

    // Main algorithm ------------------------------------------
    std::vector<std::pair<int, int>> result;
    result.reserve(values.size() / 2);
    std::sort(values.begin(), values.end());

    for (size_t k{}; k < values.size() - 1; ++k)
        if (values[k + 1] - values[k] == 2)
            result.push_back({ values[k] , values[k + 1] });
    // ------------------------------------------------------

    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start);
    std::cout << "Elapsed time: " << elapsed.count() << " ms\n\n";
    std::ofstream ofs{ "test.txt" };
    for (const auto& [v1, v2] : result) ofs << v1 << '\t' << v2 << '\n';
}

I am trying to solve the following problem using C++

1 Answers1