0
https://www.codepit.io/#/problems/5369c33df6fa9de49e5c7d0e/view? index=1
I managed to resolve this issue as follows:
#include <iostream>
#include <algorithm>
using namespace std;
int contar_pares(int y, int x[], int tam){
int cont = 0;
for(int i = tam; i > 0; i--){
for(int j = tam - 1; j >= 0; j--){
if(x[i-1] - x[j] == y){
cont++;
}
}
}
return cont;
}
int main(){
int n, k;
cin >> n >> k;
int tamanho = n;
int vetor[tamanho];
for(int i = 0; i < tamanho; i++){
cin >> vetor[i];
}
sort(vetor, vetor + tamanho);
cout << contar_pares(k, vetor, tamanho) << endl;
return 0;
}
But when I submit the time limit exceeded... Some of my colleagues managed to solve it with binary search, but my question is: how do I count how many times the k will be found inside a binary search?
Better than a binary search is using a
set
as if it were a hashtable, which even takes advantage of the resources that c++ gives it, and plays with the constraints of the problem that indicate that the numbers are distinct and do not repeat. It also increases the time complexity from O(nlogn) to O(n), and in the example of its code is O(n 2). Example of solution usingset
.– Isac