Distinct unordered pairs of an array which satisfy a condition I came across the below problem in a coding challenge:
Let's define 2 functions, \$F(i)\$ and \$Val(i,j)\$, for an array \$A\$ of size \$N\$ as follows:

$$
\begin{align}
F(i) =&amp; \sum_{j=i+1}^{N} Val(i,j) \\
\\
Val(i, j) =&amp; \begin{cases}
               1,\qquad &amp; \textrm{if } A[i] &lt; A[j] \\
               0,\qquad &amp; \textrm{otherwise}
             \end{cases}
\end{align}
$$
I need to find the number of distinct unordered pairs of elements (a,b) in array \$A\$, such that \$F(a)+F(b) \ge K\$.

Here is my solution:

#include&lt;iostream&gt;
#include&lt;cassert&gt;
#define max 1000000000

int main()
{
    unsigned int N, K;
    std::cin &gt;&gt; N;
    assert((1 &lt;= N) &amp;&amp; (N &lt;= 1000000));
    std::cin &gt;&gt; K;
    assert((0 &lt;= K) &amp;&amp; (K &lt;= max));
    unsigned int a[N], F[N];
    for(unsigned int i = 0; i &lt; N; i++)
    {
        std::cin &gt;&gt; a[i];
        assert((1 &lt;= a[i]) &amp;&amp; (a[i] &lt;= max));
    }
    int sum = 0, val = 0;
    for(unsigned int i = 0; i &lt; N; i++)
    {
        for(unsigned int j = i+1; j &lt; N; j++)
        {
            if(a[i] &lt; a[j])
            val = 1;
            else 
            val = 0;

            sum = sum + val;
        }
        F[i] = sum;
        sum = 0;
    }
    int count = 0;
    for(unsigned int i = 0; i &lt; N; i++)
    {
        for(unsigned int j = i+1; j &lt; N; j++)
        {
            if(F[i] + F[j] &gt;= K)
            count++;
        }
    }
    std::cout &lt;&lt; count &lt;&lt; std::endl;
}


While this works, I would want to know if there is a way to write optimized code which works fast even for larger inputs.
Scope


    int sum = 0, val = 0;
    for(unsigned int i = 0; i &lt; N; i++)
    {
        for(unsigned int j = i+1; j &lt; N; j++)
        {
            if(a[i] &lt; a[j])
            val = 1;
            else 
            val = 0;

            sum = sum + val;
        }
        F[i] = sum;
        sum = 0;
    }



This won't affect speed, but this would be more simply written 

    for (unsigned int i = 0; i &lt; N; i++)
    {
        int sum = 0;
        for (unsigned int j = i+1; j &lt; N; j++)
        {
            int val = 0;
            if (a[i] &lt; a[j])
            val = 1;
            else 
            val = 0;

            sum += val;
        }
        F[i] = sum;
    }


Now we only declare variables in the scope in which they are used.  

Don't create unnecessary variables

But we can actually do even better 

    for (unsigned int i = 0; i &lt; N; i++)
    {
        F[i] = 0;
        for (unsigned int j = i+1; j &lt; N; j++)
        {
            if (a[i] &lt; a[j])
            {
                F[i]++;
            }
        }
    }


We don't actually need val or sum at all.  

There is the slight possibility that constantly calculating the memory location of F[i] would add time, but I would expect any decent compiler to only set it once.  The rest of the time it will work with a register.  

This also saves some time in that it only adds if we're incrementing by 1.  If not, this does nothing.  That has the same effect as adding 0 but with fewer instructions.  Of course, your compiler may have already optimized that out.  

Many recommend always using the block form of control structures, even when there's only a single statement.  

Don't forget what you know

In this case, you are working with segments going from a point in the array to the end.  But you are looping from the beginning to the end.  What happens when you loop from the end to the beginning?  

    for (int i = N - 1; i &gt;= 0; i--)
    {
        F[i] = 0;
        for (unsigned int j = N - 1; j &gt; i; j--)
        {
            if (a[i] == a[j])
            {
                F[i] += F[j];
                break;
            }
            else if (a[i] &lt; a[j])
            {
                F[i]++;
            }
        }
    }


Now when we encounter two equal array entries we can stop looping.  


    int count = 0;
    for(unsigned int i = 0; i &lt; N; i++)
    {
        for(unsigned int j = i+1; j &lt; N; j++)
        {
            if(F[i] + F[j] &gt;= K)
            count++;
        }
    }



Same kind of insight here.  

    int n = N - K / 2;
    unsigned int count = 0;
    for (unsigned int i = 0; i &lt; n; i++)
    {
        int remainder = K - F[i];
        if (remainder &lt;= 0)
        {
            // if F[i] &gt;= K, every remaining entry will work
            count += N - i - 1;
            continue;
        }

        for (unsigned int j = N - remainder; j &gt; i; j--)
        {
            if (F[j] &gt;= remainder)
            {
                count++;
            }
        }
    }


By precalculating the remainder, we save some math in the inner loop.  And we can save some iterations of the inner loop (if remainder is too high, there is no way to add up to it at the end of the loop).  But more importantly, we can check remainder against 0.  Because if the remainder is less than or equal to zero, we can immediately say that every remaining entry will work.