# Code for calculating number of variations

Following up from my previous question where I put up a solution in brute for algorithm to this problem from codechef.

Given some number $K$ and a list of $N$ numbers, count the number of pairs ($i$, $j$) such that $1 \le i \lt j \le N$ and $|a_i − a_j | \ge K$.

• $1 \le N \le 65000$
• $1 \le K \le 10^8$
• $0 \le a_i \le 10^8$

I changed my code quite a bit and was able to get rid of that time-limit-exceded error.Thanks to the responses, here is the updated code:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

std::vector<int> testCases;
for (int i = 0; i < N; i++)
{
int TestCase;
std::cin >> TestCase;
testCases.push_back(TestCase);
}
return testCases;
}

int main(){

int args,k;
std::cin >> args >> k;

int cases = 0;

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

for(int i=1;i<args;i++){
int temp = std::abs(nums.at(i)-nums.at(i-1));
if(temp >=k){
cases = cases + i;
}else{
int j = i;
while(temp < k && j > 0){
j--;
temp = std::abs(nums.at(i)-nums.at(j));
}
if(temp >= k){
cases = cases + j + 1;
}
}
}

std::cout << cases << std::endl;
return 0;
}


But according to me the code still looks a little ugly and can be optimized more , can someone help me to identify the parts where simplification without risking the time taken can be done?

Similar to the other question, I would suggest to utilize a std::map changing your loadTestCases accordingly

std::map<int, int>loadTestCases(int N){
std::map<int, int> testCases;
int TestCase;
for (int i = 0; i < N; i++)
{
std::cin >> TestCase;
auto inserted = testCases.emplace(TestCase, 1);
if(!inserted.second) {
testCases.at(TestCase)++;
}
}
return testCases;
}


The advantage of this approach is, that you only have to traverse the keys of the std::map once and can multiply the values if there is a match.

Also given that your container is sorted you can actually skip the std::abs call, as a_i - a_j > 0 is guaranteed by that sort, if you traverse the container from the back. Also more importantly, once you find a_i - a_l > k, you automatically know, that any following pair is also valid, as by construction for an a_m < a_l we get a_i - a_m = a_i - a_l - (a_m - a_l), with (a_m - a_l) < 0.

• Note that starting from front is equivalent of a_i-a_j < 0 Aug 28, 2016 at 18:54

Optimize on design level, not source level. Your program performs the following:

2. Sort
3. Find pairs

The respective complexities are $O(n)$, $O(n~log~n)$ and $O(n^2)$ in your implementation. For now, we can ignore 1. and 2. and focus on finding pairs of distance $\geq K$ in a sorted set.

A sorted set has a couple of nice properties:

• You must only search for the first element with a sufficient distance to base. You already use that information.
• $j > i$. You already use this property too.
• When you find a pair $(i_1,j_1)$ and search for another pair $(i_2,j_2)$ with $i_2 \geq i_1$, $j_2 \geq j_1$ must also hold true.

You can base your inner loop on $j_1$ instead of $i_2$, which eliminates it altogether, making the search $O(n)$. The result are two pointers that traverse the set in a single pass. The pointers keep a distance of $K$

• If $d < K$, the leading pointer advances.
• If $d \geq K$, the trailing pointer advances.

and are therefore guaranteed to hit every pair of interest exactly once.

int countPairs(const std::vector<int> sortedNums, int k)
{
const size_t size = sortedNums.size();
size_t trailingIndex = 0;
int count = 0;

{
if (sortedNums[leadingIndex] - sortedNums[trailingIndex] < k)
{
}
else
{
trailingIndex++;
}
}
return count;
}


Execution time is reduced by an order of magnitude and well within the required limit.

int main(){
int args,k;
std::cin >> args >> k;


If you want to improve it any further, you must focus on the sorting algorithm which became the limiting factor ($O(n~log~n)$ vs. $O(n)$). You may consider using an Integer Sorting algorithm instead of the generic comparison sort.