Find greatest number in array that is a product of some two elements in the same array

Question

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 < a.Length; ++i)
            {
                for (int j = i + 1; j < a.Length; ++j)
                {
                    int temp = a[i] * a[j];
                    if (a.Contains(temp) && temp > x)
                    {
                        x = temp;
                    }
                }
            }
            return x;
        }
    }
}

using NUnit.Framework;

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

    }
}

Answer 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) && temp > x

should be written as

temp > x && 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 < input.Length && input[i] == value);
    return i;
}

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

    Array.Sort(input);

    if (input[0] < 0)
    {
        throw new ArgumentException("Input cannot contain negative numbers.");
    }

    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 < input.Length - 1 && input[imin] == 1)
    {
        // if there is "1" in the input, the greatest element of input is the result
        // except if there is just one "1" 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 > imin; --pi)
    {
        int product = input[pi];

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

        // assume values before bmax are some "a", then look for "b"
        for (int ai = imin; ai < 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 "b" value in the reasonable range (bmin, ai)
            for (int bi = bmin; bi < ai; ++bi)
            {
                int b = input[bi];

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

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

            // let's turn the naive "for bi" loop into log(n)

            // searchfor a "b" 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 "a" then the current one
            // we are inevitably only going to find a smaller "b"
            int bmin = ai;
            while (bmax > bmin)
            {
                // int bi = (bmin + bmax) / 2;
                // variant with no overflow of index (for very large arrays):
                int bi = (bmin / 2 + bmax / 2) + ((bmin % 2) & (bmax % 2));

                int b = input[bi];

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

                if (b < 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 "not found" 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 <= r < 1000. Now 0 <= r < 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 |

Answer 2

If you sort you array, and after that your temp is greater than max value from that array (last item), then you can break your loops earlier and save some computation. Here is an example:

using System;
using System.Linq;

namespace Exercise
{
    public static class TestClass
    {
        public static int NewMaxPairProduct(int[] a)
        {
            Array.Sort(a);

            int x = -1;
            int maxItemInArray = a[a.Length - 1];

            for (int i = 0; i < a.Length; ++i)
            {
                for (int j = i + 1; j < a.Length; ++j)
                {
                    int temp = a[i] * a[j];

                    if (a.Contains(temp) && temp > x)
                        x = temp;

                    if (temp >= maxItemInArray)
                    {
                        if (j == i + 1) // break both loops - first iteration is greater then max item
                            return x;

                        break; // break only inner loop - we have to verify other options
                    }
                }
            }

            return x;
        }

        public static int OldMaxPairProduct(int[] a)
        {
            int x = -1;

            for (int i = 0; i < a.Length; ++i)
            {
                for (int j = i + 1; j < a.Length; ++j)
                {
                    int temp = a[i] * a[j];

                    if (a.Contains(temp) && temp > x)
                    {
                        x = temp;
                    }
                }
            }
            return x;
        }
    }
}

Benchmark .net Performance test:

using System;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace Exercise
{
    public class Benchmark
    {
        [Params(10, 100, 1000)]
        public int N { get; set; }

        private int[] data;

        [GlobalSetup]
        public void GlobalSetup()
        {
            Random random = new Random();
            data = Enumerable.Repeat(0, N).Select(i => random.Next(1000)).ToArray();
        }

        [Benchmark]
        public int NewTest() => TestClass.NewMaxPairProduct(data);

        [Benchmark]
        public int OldTest() => TestClass.OldMaxPairProduct(data);
    }

    public static class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<Benchmark>();
        }
    }
}

Results:

|  Method |    N |             Mean |         Error |        StdDev |
|-------- |----- |-----------------:|--------------:|--------------:|
| NewTest |   10 |         126.3 ns |       2.53 ns |       2.91 ns |
| OldTest |   10 |         483.8 ns |       6.92 ns |       6.13 ns |
| NewTest |  100 |       1,519.0 ns |       8.21 ns |       7.68 ns |
| OldTest |  100 |     125,406.8 ns |   1,420.11 ns |   1,258.89 ns |
| NewTest | 1000 |     293,878.8 ns |     250.04 ns |     195.22 ns |
| OldTest | 1000 | 137,166,762.5 ns | 713,905.95 ns | 632,859.03 ns |

So with the bigger array you have bigger performance gain. Of course this was tested on random arrays so the results may vary.

Answer 3

O(n√n) solution (and a faster one below)

---

First, a quick note about your implementation: it doesn't ensure that the returned product is the maximal product, it just returns the last product it finds. Your tests are too simple to detect this bug.

---

Step 1: reduce the time complexity from O(n^3) to O(n^2) (at the cost of increasing memory complexity to O(n)) by creating a hash table with all the numbers from the array, so your contains checks can be O(1) instead of O(n).

Sort the array and start checking from the biggest number so you can stop as soon as you find a product.

public static int MaxPairProduct(int[] input)
{
    Array.Sort(input);
    if(input[input.Length - 1] == 0)
    {
        return input.Length > 1 ? 0 : -1;
    }
    int minIndex = -1;
    while (input[++minIndex] == 0);
    HashSet<int> hashSet = new HashSet<int>(input);

    for (int i = input.Length - 1; i > 0; i--)
    {
        int product = input[i];
        for (int j = i - 1; j >= minIndex; j--)
        {
            if (product % input[j] == 0 && hashSet.Contains(product / input[j]))
            {
                return product;
            }
        }
    }

    return input[0] == 0 && input.Length > 1 ? 0 : -1;
}

Step 2: decrease the time complexity to O(n√n) on average (there are O(n^2) edge cases) by making the inner loop start from index 0 and continue only until it reaches the square root of product, because by then you will have checked all the multiplications that could possibly produce product. Any number bigger than the root needs to be multiplied by a number smaller than the root, and they were all seen already.

public static int MaxPairProduct(int[] input)
{
    Array.Sort(input);
    if(input[input.Length - 1] == 0)
    {
        return input.Length > 1 ? 0 : -1;
    }
    int minIndex = -1;
    while (input[++minIndex] == 0);
    HashSet<int> hashSet = new HashSet<int>(input);

    for (int i = input.Length - 1; i > 0; i--)
    {
        int product = input[i];
        int root = (int)Math.Sqrt(product);
        int j = minIndex;
        for (; j < input.Length && input[j] < root; j++)
        {
            if (product % input[j] == 0 && hashSet.Contains(product / input[j]))
            {
                return product;
            }
        }
        if(input[j] == root && input[j+1] == root && product % root == 0)
        {
            return product;
        }
    }

    return input[0] == 0 && input.Length > 1 ? 0 : -1;
}

If you want O(1) memory complexity you can use binary search instead of HashSet, giving you time complexity of O(n√n log n).

Update: bug fix

The code above doesn't account for rounding errors, for example (int)Math.Sqrt(6) == 2 and 6 % 2 == 0 but 2 * 2 != 6.

public static int MaxPairProduct(int[] input)
{
    Array.Sort(input);

    if (input[input.Length - 1] == 0)
    {
        return input.Length > 1 ? 0 : -1;
    }

    int minIndex = -1;
    while (input[++minIndex] == 0);
    HashSet<int> hashSet = new HashSet<int>(input);

    for (int i = input.Length - 1; i > minIndex; i--)
    {
        int product = input[i];
        if(product == 1)
        {
            return input[i-1];
        }
        int root = (int)Math.Sqrt(product);
        // remember if root was rounded, to avoid errors: (int)√6 == 2 but 2*2 != 6
        bool rootIsPrecise = root * root == product;
        int j = minIndex;
        for (; input[j] <= root; j++)
        {
            if (product % input[j] == 0)
            {
                if(input[j] == root && rootIsPrecise)
                {
                    if(j + 1 < input.Length && input[j+1] == root)
                    {
                        return product;
                    }
                }
                else if(hashSet.Contains(product / input[j]))
                {
                    return product;
                }
            }
        }
    }

    return input[0] == 0 && input.Length > 1 ? 0 : -1;
}

O(n√n log n) solution - but faster than the above

Apparently using HashSet is incredibly slow (despite the supposed O(1) search), so I replaced it with a binary search.

public static int MaxPairProduct(int[] input)
{
    Array.Sort(input);
    if (input[input.Length - 1] == 0)
    {
        return input.Length > 1 ? 0 : -1;
    }

    int minIndex = -1;
    while (input[++minIndex] == 0);
    for (int i = input.Length - 1; i > minIndex; i--)
    {
        int product = input[i];
        if(product == 1)
        {
            return input[i-1];
        }
        int root = (int)Math.Sqrt(product);
        bool rootIsPrecise = root * root == product;
        int j = minIndex;
        for (; input[j] <= root; j++)
        {
            if (product % input[j] == 0)
            {
                if(input[j] == root && rootIsPrecise)
                {
                    if(j + 1 < input.Length && input[j+1] == root)
                    {
                        return product;
                    }
                }
                else if(BinarySearch(input, product / input[j]))
                {
                    return product;
                }
            }
        }
    }

    return input[0] == 0 && input.Length > 1 ? 0 : -1;
}

public static bool BinarySearch(int[] arr, int key)
{
    int min = 0, max = arr.Length - 1, mid;
    while(min < max)
    {
        mid = max + (min - max) / 2;
        if(arr[mid] > key)
        {
            max = mid - 1;
        }
        else
        {
            min = mid;
        }
    }
    return arr[max] == key;
}

Answer 4

There is not much to add to the other answers. Your code is well written and easy to understand, but as a brute force algorithm it has its limitation in real world use - for larger data sets at least.

---

The name should be MaxPairProduct (PascalCase) instead of maxPairProduct.

---

There is maybe an issue (that applies to the other answers as well):

For the dataset:

int[] data = { 1, 2, 3 }

it returns 3, but it should return -1, if the multiplier, multiplicand and product must be distinct entries in the data set? The dataset { 1, 2, 3, 3 } should return 3.

Similar

int[] data = { 1, 2, 2, 3, 4, 5 };

should return 4 but returns 5.

The above is somehow inconsistent with:

int[] data = { 2, 3, 4 };

that correctly results in -1.

---

Below is an implementation that handles the above problem, and also prevent a possible overflow when multiplying:

static int MaxPairProduct(int[] a)
{
  Array.Sort(a);

  int product = -1;
  int multiplier = -1;
  int multiplicand;

  for (int i = a.Length - 1; i > 1; --i)
  {
    if (a[i] == product) continue;
    product = a[i];

    for (int j = 0; j < i; ++j)
    {
      if (a[j] == multiplier) continue;
      multiplier = a[j];

      if (multiplier == 0) continue;
      multiplicand = product / multiplier;
      if (product % multiplier == 0 && Array.IndexOf(a, multiplicand, j + 1, i - j - 1) > j)
      {
        return product;
      }
      if (multiplicand < multiplier)
        break;
    }
  }

  return -1;
}

Answer 5

You're doing micro-optimization, which means, you don't have any major optimization on your hands more than you've done already. All other optimizations would only impact big-data, but for average data, it won't be noticeable. Or that's what I think.

But, I agree, sorting the array would be much beneficial to your code as dealing with unsorted array would return unexpected results along with producing a disaster code experience. So, sort the array first, ascending or descending, all depends on your data-process.

Then, instead of looping and multiplying, you can try to decrease the amount of looping rounds by taking the max product then based on that value, do your looping while keeping in mind :

• the value should be less than the max
• the value should not be negative.
• avoid converting between collections types (like IEnumerable to Array).
• break the loop if the multiplier and multiplicand has been found.

This would cut your looping timing.

I'll demonstrate my idea.

your current code have 2 for loops, and also used Contains which has an also a loop.

Here is the Contains has something like this code :

public static bool Contains(int[] array, int number) {

    if(array == null) return false;

    for(var x = 0; x < array.Length; x++)
    {
        if (array[x].Equals(number)) { return true; }        
    }

    return false;
}

This would but your total iterations around 65 iterations (with the provided sample). and that's with the Contains iterations. This is only on 5 elements, which means each element would iterate about 13 times. This is too much iterations.

to reduce that, we can take the highest values first, then iterate over the array based on these values. In your case, you can take the highest 3 values, and loop over them.

So, re-thinking over, the logic would be something like :

1. take the highest 3 values and store them in descending order.
2. for each max value, iterate over the array to check wither there is a multiplier and multiplicand for it or not.
3. if there is, return this max. (which would end this process).

with that in mind, we can start with something like this :

public static int maxPairProduct(int[] a)
{
    foreach (var number in a.OrderByDescending(x => x).Skip(0).Take(3))
    {
        for (var j = 0; j < a.Length; j++)
        {
            // skip if the numbers are equal or bigger than the max number
            if (j+1 >= a.Length || a[j] >= number || a[j + 1] >= number) { continue; }

            if (a[j] * a[j + 1] == number) { return number; }
        }

    }

    return -1;
}

With this, we reduced the iterations to the minimum.

UPDATE :

if you want to extend the Take so it will take 3 max integers and do the tests until it finds the product multiplier and multiplicand you can do this :

public static int GetMaxPair(int[] a)
{
    var skip = 0; 
    var take = 3;        
    var descOrder = a.OrderByDescending(x => x); 

    do 
    {
        foreach(var number in descOrder.Skip(skip).Take(take))
        {
            for (var j = 0; j < a.Length; j++)
            {
                // skip if the numbers are equal or bigger than the max number
                if (j+1 >= a.Length || a[j] >= number || a[j + 1] >= number) { continue; }

                if (a[j] * a[j + 1] == number) { return number; }
            }                             
        }

        skip += take;

        if(skip > a.Length) { return -1; }
    }
    while(true);
}