Count the number of ways to select two numbers in an efficient algorithm

One quicker solution would be to sort the array first, then iterate over the sorted array, and for each element, only visit the elements to its right until the difference exceeds 31.

The sort can probably be done by sorting count (since you have 1 ≤ V [i] ≤ 10,000). This way you get linear time for the sorting part. It might not be necessary though (maybe for a quick point of view it's enough to get all the points).

Alternatively, you can do a trick for the inner loop (the "right of the current element" part). Note that if S [i + k] -S [i] 32 then S [i + k] -S [i + 1] <32, where S is the sorted version of V. With this trick, the whole algorithm becomes linear.

This can be done with a constant number of passes over the data and can in fact be done without compromising the "spacing" value (32 in your case). This is done by filling in an array, where a[i] = a[i-1] + number_of_times_i_appears_in_the_data

- informally, a[i]

contains the total number of elements that are less than / equal to i

.

Code (for one test case):

static int UPPER_LIMIT = 10001;
static int K = 32;
int frequencies[UPPER_LIMIT] = {0}; // O(U)
int n;
std::cin >> n;
for (int i = 0; i < n; i++) { // O(n)
 int x;
 std::cin >> x;
 frequencies[x] += 1;
}
for (int i = 1; i < UPPER_LIMIT; i++) { // O(U)
    frequencies[i] += frequencies[i-1];
}
int count = 0;
for (int i = 1; i < UPPER_LIMIT; i++) { // O(U)
  int low_idx = std::max(i-32, 0);
  int number_of_elements_with_value_i = frequencies[i] - frequencies[i-1];
  if (number_of_elements_with_value_i == 0) continue;
  int number_of_elements_with_value_K_close_to_i =
      (frequencies[i-1] - frequencies[low_idx]);
  std::cout << "i: " << i << " number_of_elements_with_value_i: " << number_of_elements_with_value_i << " number_of_elements_with_value_K_close_to_i: " << number_of_elements_with_value_K_close_to_i << std::endl;
  count += number_of_elements_with_value_i * number_of_elements_with_value_K_close_to_i;
  // Finally, add "duplicates" of i, this is basically sum of arithmetic 
  // progression with d=1, a0=0, n=number_of_elements_with_value_i
  count += number_of_elements_with_value_i * (number_of_elements_with_value_i-1) /2;
}
std::cout << count;

      

        
        
        
      

    

Complete working example on IDEone .

This solution can be thought of as O (N) to process N input numbers and a constant over time to process input:

#include <iostream>
using namespace std;

void solve()
{
    int a[10001] = {0}, N, n, X32 = 0, ret = 0;
    cin >> N;
    for (int i=0; i<N; ++i)
    {
        cin >> n;
        a[n]++;
    }

    for (int i=0; i<10001; ++i)
    {
        if (i >= 32)
            X32 -= a[i-32];
        if (a[i])
        {
            ret += a[i] * X32;
            ret += a[i] * (a[i]-1)/2;
            X32 += a[i];
        }
    }
    cout << ret << endl;
}

int main()
{
    int T;
    cin >> T;
    for (int i=0 ; i<T ; i++)
        solve();
}

      

        
        
        
      

    

run this code on ideone

Explanation of solution: a[i]

shows how many times i

was in the input rows. Then you loop through the entire array and X32 keeps track of the number of elements that range from i

. The only tricky part is to calculate correctly when multiple I repeated several times a[i] * (a[i]-1)/2

. What is it.

You can sort and then use a tear-off loop to the end when the range deviates.

int main()
{
    int t;
    cin>>t;

    while(t--){
        int n,c=0;
        cin>>n;

        int ar[n];
        for(int i=0;i<n;i++)
            cin>>ar[i];

        sort(ar,ar+n);

        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(ar[j]-ar[i] < 32)
                    c++;
                else
                    break;
            }
        }
        cout<<c<<endl;
    }
}

      

        
        
        
      

    

Or you can use a hash array for the range and mark the occurrence of each element and then loop around and check for each element, i.e. if x = 32-y is present or not.

A good approach here is to split the numbers into separate buckets:

constexpr int limit = 10000;
constexpr int diff = 32;
constexpr int bucket_num = (limit/diff)+1;
std::array<std::vector<int>,bucket_num> buckets;

cin>>n;
int number;
for(i=0;i<n;i++)
{
    cin >> number;
    buckets[number/diff].push_back(number%diff);
}

      

        
        
        
      

    

Obviously, the numbers in the same bucket are close enough to each other to meet the requirement, so we can just count all the pairs:

int result = std::accumulate(buckets.begin(), buckets.end(), 0,
                  [](int s, vector<int>& v){ return s + (v.size()*(v.size()-1))/2; });  

      

        
        
        
      

    

Numbers that are in non-contiguous buckets cannot form acceptable pairs, so we can simply ignore them.

This leaves the last corner case - adjacent buckets - which can be solved in different ways:

for(int i=0;i<bucket_num-1;i++)
   if(buckets[i].size() && buckets[i+1].size())
      result += adjacent_buckets(buckets[i], buckets[i+1]);

      

        
        
        
      

    

Personally, I like the "spawn rate" approach at the scale of a single cabinet, but there may be better options:

int adjacent_buckets(const vector<int>& bucket1, const vector<int>& bucket2)
{
    std::array<int,diff> pairs{};
    for(int number : bucket1)
     {
         for(int i=0;i<number;i++)
            pairs[i]++;
     }

    return std::accumulate(bucket2.begin(), bucket2.end(), 0,
                           [&pairs](int s, int n){ return s + pairs[n]; }); 
}

      

        
        
        
      

    

This function first creates an array of "numbers from the bottom bucket that are close enough to i

" and then sums the values ​​from that array that correspond to the top numbers of the bucket.

In general, this approach is O (N) in complexity, at best it only takes one pass, and in general should be fast enough.

An example of a working ideal

You have to start by sorting the input.

Then, if your inner loop detects that the distance is growing above 32, you can drop it.