Find greatest number in array that is a product of some two elements in the same array Given an array a, find the greatest number in a that is a product of two elements in a. If there are no two elements in a that can be multiplied to produce another element contained in a, return -1.


I am trying to get this to run as fast as possible.  I assume there is some math algorithm or formula to do this that I am unaware of.  This is the way I know how to find this answer.  However, I assume this would take a long time if the length of the array was huge.  Is there a faster way to do this?  I have provided the test.

using System;
using System.Linq;

namespace Exercise
{
    public static class Program
    {
        public static int maxPairProduct(int[] a)
        {
            int x = -1;

            for (int i = 0; i &lt; a.Length; ++i)
            {
                for (int j = i + 1; j &lt; a.Length; ++j)
                {
                    int temp = a[i] * a[j];
                    if (a.Contains(temp) &amp;&amp; temp &gt; x)
                    {
                        x = temp;
                    }
                }
            }
            return x;
        }
    }
}


using NUnit.Framework;

namespace Exercise
{
    public class SuccessTests
    {
        [Test]
        public static void TestOne() =&gt; Assert.That(Program.maxPairProduct(new int[] { 10, 3, 5, 30, 35 }), Is.EqualTo(30));
        public static void TestTwo() =&gt; Assert.That(Program.maxPairProduct(new int[] { 2, 5, 7, 8 }), Is.EqualTo(-1));

    }
}
Sort it
As @Peska suggested, sort the array first. But sort it descendand, or simply iterate in reverse order.
Overflow
The multiplication of integers can overflow. It would be wiser to approach the iterations from product, divide by one element and check if the division equals second element, but only if product modulo first element is zero.
Contains() checks too much
First of all.
a.Contains(temp) &amp;&amp; temp &gt; x

should be written as
temp &gt; x &amp;&amp; a.Contains(temp)

The Contains call is O(n), we want to avoid this as much as possible, as it is turning the entire algorithm to O(n^3). In sorted input, we can make some restrictions and which elements we search through. We can actually deploy a binary search, introducing another loop instead of call to Contains, but this loop will be O(log(n)). In the code I have a naive variant that is commented out and is still O(n), but still checks much less then full Contains scan.
// we will use this to skip duplicate elements in forward iterations
private static int NextDistinctElementIndex(int[] input, int i)
{
    int value = input[i];
    do
    {
        ++i;
    } while (i &lt; input.Length &amp;&amp; input[i] == value);
    return i;
}

public static int SlepicMaxPairProduct(int[] input)
{
    if (input.Length &lt; 2)
    {
        // there's never product of two, if there are no two
        return -1;
    }

    Array.Sort(input);

    if (input[0] &lt; 0)
    {
        throw new ArgumentException(&quot;Input cannot contain negative numbers.&quot;);
    }

    int result = -1;
    int imin = 0;

    if (input[0] == 0)
    {
        // if first element after sort is zero, the result will be at least zero
        result = 0;
        // and we will never have to search for zeroes
        imin = NextDistinctElementIndex(input, 0);
    }

    if (imin &lt; input.Length - 1 &amp;&amp; input[imin] == 1)
    {
        // if there is &quot;1&quot; in the input, the greatest element of input is the result
        // except if there is just one &quot;1&quot; and zero(es)
        return input[input.Length - 1];
    }

    // start examining the sorted input from greatest element
    // and assume the values to potentialy be the product we are looking for
    for (int pi = input.Length - 1; pi &gt; imin; --pi)
    {
        int product = input[pi];

        // exclusive index of the greatest element that is reasonable to search for a &quot;b&quot; value
        int bmax = pi;

        // assume values before bmax are some &quot;a&quot;, then look for &quot;b&quot;
        for (int ai = imin; ai &lt; bmax; ++ai)
        {
            int a = input[ai];

            // if product is not divisible by a, we won't find any b
            if (product % a != 0)
            {
                continue;
            }

            int expectedB = product / a;

            /*
            // search for a &quot;b&quot; value in the reasonable range (bmin, ai)
            for (int bi = bmin; bi &lt; ai; ++bi)
            {
                int b = input[bi];

                if (b == expectedB)
                {
                    return product;
                }

                if (b &gt; expectedB)
                {
                    bmin = bi;
                    break;
                }
            }*/

            // let's turn the naive &quot;for bi&quot; loop into log(n)

            // searchfor a &quot;b&quot; value using bisection in the reasonable range (bmin, bmax)
            // and export new values of bmax to the outer loop
            // because if we will search for a greater &quot;a&quot; then the current one
            // we are inevitably only going to find a smaller &quot;b&quot;
            int bmin = ai;
            while (bmax &gt; bmin)
            {
                // int bi = (bmin + bmax) / 2;
                // variant with no overflow of index (for very large arrays):
                int bi = (bmin / 2 + bmax / 2) + ((bmin % 2) &amp; (bmax % 2));

                int b = input[bi];

                if (b == expectedB)
                {
                    return product;
                }

                if (b &lt; expectedB)
                {
                    bmin = bi + 1;
                }
                else
                {
                    bmax = bi;
                }
            }
        }
    }

    return result;
}

In conclusion, we have limited the searched space to a great degree and turned the algorithm from O(n^3) to O((n^2) * log(n)).
|       Method |    N |               Mean |            Error |           StdDev |
|------------- |----- |-------------------:|-----------------:|-----------------:|
|    PeskaTest |   10 |           215.3 ns |          3.61 ns |          3.38 ns |
| MilliornTest |   10 |         4,868.0 ns |         88.16 ns |        134.64 ns |
|   SlepicTest |   10 |           264.6 ns |          3.57 ns |          3.34 ns |
|    PeskaTest |  100 |        56,954.4 ns |      1,131.18 ns |      1,548.37 ns |
| MilliornTest |  100 |     4,352,830.7 ns |     76,663.28 ns |     94,149.39 ns |
|   SlepicTest |  100 |        16,452.8 ns |         86.02 ns |         76.25 ns |
|    PeskaTest | 1000 |    27,821,365.8 ns |    349,019.38 ns |    309,396.59 ns |
| MilliornTest | 1000 | 4,193,838,300.0 ns | 43,784,319.26 ns | 40,955,879.40 ns |
|   SlepicTest | 1000 |        50,757.2 ns |        244.00 ns |        203.76 ns |

PS: Based on return value -1 meaning &quot;not found&quot; I assume the input cannot contain negative numbers, otherwise it cannot work like this (where I assume that if zero is present it is on index 0, ...)
PS2: It is not very nice that the implementation sorts the array for the caller. It may be wise to provide the method expecting the input already sorted and provide a wrapper that creates a sorted copy and passes it to this method that expects sorted input. It will be more expensive because of copying and allocating new array, but for big inputs, this should be neglegable (because it is O(n) which is neglegable compared to O(n^2*log(n)) while making it error safe, immutable for the caller, thus more transparent for him, and offering the method that expects sorted input makes it more flexible/efficient for callers that already sorted their input.
EDIT:
New bench results including @potato's solution (2nd snippet). Mine still seems faster although according to potato's big-O, his should be faster. Not sure what's going on yet...
|       Method |    N |               Mean |            Error |           StdDev |
|------------- |----- |-------------------:|-----------------:|-----------------:|
|    PeskaTest |   10 |           209.6 ns |          1.25 ns |          1.11 ns |
| MilliornTest |   10 |         5,168.6 ns |         58.73 ns |         54.93 ns |
|   SlepicTest |   10 |           256.8 ns |          1.12 ns |          0.99 ns |
|   PotatoTest |   10 |           539.0 ns |          1.25 ns |          1.04 ns |
|    PeskaTest |  100 |         3,567.1 ns |         45.20 ns |         37.75 ns |
| MilliornTest |  100 |     4,806,710.5 ns |     13,092.42 ns |     10,932.77 ns |
|   SlepicTest |  100 |         5,039.0 ns |         58.10 ns |         48.52 ns |
|   PotatoTest |  100 |         6,141.9 ns |        111.06 ns |         86.71 ns |
|    PeskaTest | 1000 |    26,678,273.6 ns |    502,308.33 ns |    419,450.21 ns |
| MilliornTest | 1000 | 4,798,816,196.0 ns | 29,527,973.10 ns | 39,418,995.96 ns |
|   SlepicTest | 1000 |        44,601.9 ns |        407.09 ns |        360.87 ns |
|   PotatoTest | 1000 |        84,168.8 ns |        207.99 ns |        173.69 ns |

|     Method |     N |        Mean |     Error |    StdDev |
|----------- |------ |------------:|----------:|----------:|
| SlepicTest |  1000 |    49.88 us |  0.123 us |  0.103 us |
| PotatoTest |  1000 |    86.66 us |  1.121 us |  0.994 us |
| SlepicTest |  2000 |   119.67 us |  0.628 us |  0.557 us |
| PotatoTest |  2000 |   193.52 us |  0.530 us |  0.470 us |
| SlepicTest |  4000 |   279.29 us |  4.180 us |  3.705 us |
| PotatoTest |  4000 |   409.23 us |  1.443 us |  1.127 us |
| SlepicTest |  8000 |   563.60 us |  1.117 us |  0.990 us |
| PotatoTest |  8000 |   859.76 us |  4.800 us |  4.490 us |
| SlepicTest | 16000 | 1,201.41 us | 12.686 us | 11.867 us |
| PotatoTest | 16000 | 1,659.58 us |  8.473 us |  7.511 us |

|     Method |      N |      Mean |     Error |    StdDev |
|----------- |------- |----------:|----------:|----------:|
| SlepicTest | 100000 |  8.657 ms | 0.0556 ms | 0.0464 ms |
| PotatoTest | 100000 | 10.628 ms | 0.0301 ms | 0.0266 ms |

|     Method |       N |     Mean |   Error |  StdDev |
|----------- |-------- |---------:|--------:|--------:|
| SlepicTest | 1000000 | 101.7 ms | 0.41 ms | 0.36 ms |
| PotatoTest | 1000000 | 119.1 ms | 0.30 ms | 0.25 ms |

|     Method |        N |    Mean |    Error |   StdDev |
|----------- |--------- |--------:|---------:|---------:|
| SlepicTest | 10000000 | 1.266 s | 0.0048 s | 0.0043 s |
| PotatoTest | 10000000 | 1.446 s | 0.0194 s | 0.0172 s |

Those were with random numbers r: 0 &lt;= r &lt; 1000.
Now 0 &lt;= r &lt; N:
|     Method |        N |           Mean |       Error |      StdDev |
|----------- |--------- |---------------:|------------:|------------:|
| SlepicTest |    10000 |       726.4 us |     2.90 us |     2.57 us |
| PotatoTest |    10000 |     1,055.5 us |     4.55 us |     3.80 us |
| SlepicTest |   100000 |     9,056.1 us |    33.79 us |    31.61 us |
| PotatoTest |   100000 |    11,992.9 us |    58.15 us |    48.55 us |
| SlepicTest |  1000000 |   107,084.9 us |   473.48 us |   419.73 us |
| PotatoTest |  1000000 |   139,090.3 us |   376.83 us |   352.48 us |
| SlepicTest | 10000000 | 1,306,931.0 us | 2,585.99 us | 2,018.97 us |
| PotatoTest | 10000000 | 1,648,109.2 us | 7,627.77 us | 7,135.02 us |