Improving optimization of nested loop

Question

I'm making a simple program to calculate the number of pairs in an array that are divisible by 3 array length and values are user determined.

Now my code is perfectly fine. However, I just want to check if there is a faster way to calculate it which results in less compiling time?

As the length of the array is 10^4 or less compiler takes less than 100ms. However, as it gets more to 10^5 it spikes up to 1000ms so why is this? and how to improve speed?

#include <iostream>

using namespace std;

int main()
{
    int N, i, b;
    b = 0;
    cin >> N;

    unsigned int j = 0;
    std::vector<unsigned int> a(N);
    for (j = 0; j < N; j++) {
        cin >> a[j];
        if (j == 0) {
        }

        else {
            for (i = j - 1; i >= 0; i = i - 1) {
                if ((a[j] + a[i]) % 3 == 0) {
                    b++;
                }
            }
        }
    }

    cout << b;

    return 0;
}

Answer 1

Your algorithm has O(N^2) complexity. There is a faster way.

(a[i] + a[j]) % 3 == ((a[i] % 3) + (a[j] % 3)) % 3

Thus, you need not know the exact numbers, you need to know their remainders of division by three only. Zero remainder of the sum can be received with two numbers with zero remainders (0 + 0) and with two numbers with remainders 1 and 2 (1 + 2).

The result will be equal to r[1]*r[2] + r[0]*(r[0]-1)/2 where r[i] is the quantity of numbers with remainder equal to i.

int r[3] = {};
for (int i : a) {
    r[i % 3]++; 
}
std::cout << r[1]*r[2] + (r[0]*(r[0]-1)) / 2;

The complexity of this algorithm is O(N).

Answer 2

I've encountered this problem before, and while I don't find my particular solution, you could improve running times by hashing.

The code would look something like this:

// A C++ program to check if arr[0..n-1] can be divided
// in pairs such that every pair is divisible by k.
#include <bits/stdc++.h>
using namespace std;

// Returns true if arr[0..n-1] can be divided into pairs
// with sum divisible by k.
bool canPairs(int arr[], int n, int k)
{
    // An odd length array cannot be divided into pairs
    if (n & 1)
         return false;

    // Create a frequency array to count occurrences
    // of all remainders when divided by k.
    map<int, int> freq;

    // Count occurrences of all remainders
    for (int i = 0; i < n; i++)
        freq[arr[i] % k]++;

    // Traverse input array and use freq[] to decide
    // if given array can be divided in pairs
    for (int i = 0; i < n; i++)
    {
        // Remainder of current element
        int rem = arr[i] % k;

        // If remainder with current element divides
        // k into two halves.
        if  (2*rem == k)
        {
            // Then there must be even occurrences of
            // such remainder
            if (freq[rem] % 2 != 0)
                return false;
        }

        // If remainder is 0, then there must be two 
        // elements with 0 remainder
        else if (rem == 0)
        {
           if (freq[rem] & 1)           
               return false;
        }        

        // Else number of occurrences of remainder
        // must be equal to number of occurrences of
        // k - remainder
        else if (freq[rem] != freq[k - rem])
            return false;
    }
    return true;
}

/* Driver program to test above function */
int main()
{
    int arr[] =  {92, 75, 65, 48, 45, 35};
    int k = 10;
    int n = sizeof(arr)/sizeof(arr[0]);
    canPairs(arr, n, k)? cout << "True": cout << "False";
    return 0;
}

That works for a k (in your case 3) But then again, this is not my code, but the code you can find in the following link. with a proper explanation. I didn't just paste the link since it's bad practice I think.