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;
}

If your code works correctly, and you want only to improve it, consider asking on [codereview.stackexchange.com](https://codereview.stackexchange.com/). — Algirdas Preidžius, Oct 11 '17 at 20:11
Side note. If you optimise your code you are probably improving ‘execution time’. Compiling time isn’t normally an factor as this only has to happen once when you build the program :) — Michael Hancock, Oct 11 '17 at 20:14
https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard — Manvir, Oct 11 '17 at 20:18
Consider using https://godbolt.org/ to see how different compilers and different flags will optimize your code. — François Andrieux, Oct 11 '17 at 20:20
@Renato And putting it more generally, never change the code in a question. The only change anyone should ever make to the code in a question is to clean up the formatting, and even then only if the original formatting is unreadable. Don't even clean up the formatting if it is just a cosmetic judgment call. If you have improvements to make to the code in a question, put them in an answer. — Michael Geary, Oct 12 '17 at 05:25
@Michael Geary The change was unintended. The code should not have been modified. I *know* what shouldn't be done, but was corrected before I realized the mess I had posted. — Renato, Oct 16 '17 at 18:22

DAle · Accepted Answer · 2017-10-12T05:59:33.330

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).

score 0 · Answer 2 · answered Oct 11 '17 at 20:26

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.

Improving optimization of nested loop

2 Answers2