Find the maximum product between two different numbers in an array. The product also has to be a multiple of 3

Question

The code below finds the biggest product pair, but it still doesn't make sure that the numbers are different and that the product is a multiple of 3.

let arr = [1, 4, 3, 6, 9, 9];

For instance, the answer for the above array should be 9x6=54 (product of the highest different numbers that is also multiple of 3) but my current code result is 9x9=81.

Important observation, the given array can contain positive and negative numbers also.

Does anyone have any tips?

// product in array of Integers
function maxProduct(arr, n)
{
     
    // Sort the array
    arr.sort(function(a, b){return a - b});
     
    let  num1, num2;
     
    // Calculate product of two smallest numbers
    let sum1 = arr[0] * arr[1];
     
    // Calculate product of two largest numbers
    let sum2 = arr[n - 1] * arr[n - 2];
     
    // print the pairs whose product is greater
    if (sum1 > sum2)
    {
        num1 = arr[0];
        num2 = arr[1];
    }
    else
    {
        num1 = arr[n - 2];
        num2 = arr[n - 1];
    }
    document.write("Max product pair = " +
                 "{" + num1 + "," + num2 + "}");
}

</script>

Answer 1

You can do something like this:

1. Split the array into multiples_of_3 (M3) and non_multiples_of_3 (NM3).
2. Find top 2 largest numbers from M3 and NM3. Your answer will always include largest M3.
3. Note that your use case needs distinct largest numbers. That needs to be taken care of. eg. In python, you can convert input list to set etc.
4. Find the largest number of the remaining 3.

This will always work for an array of positive numbers. If there are -ve numbers as well, then, -ve numbers will only be part of solution if both selected are -ve. In which case, you can repeat the steps for only -ve numbers in the input and compare.

Complexity: O(n) : 2 traversals, one to split the array into M3 and NM3, next to select largest M3 and 3 other candidates for +ve and -ve values.

Answer 2

An O(N) time, O(1) extra space algorithm:

1. Traverse the array, keep track of two variables: max_multiple_of_three and min_multiple_of_three
2. Traverse the array, keep track of two variables: largest_number_in_array (which shouldn't be equal to max_multiple of three) and smallest_number_in_array (which shouldn't be equal to min_multiple_of_three)
3. The answer will be either max_multiple_of_three * largest_number_in_array or min_multiple_of_three * smallest_number_in_array