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>
´´´´

CodePudding user response：

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.

CodePudding user response：

You can use a simple algorithm

1. Sort the array in reverse order
2. Pick the first two distinct numbers (let them be x and y with x>y)
3. If either is a multiple of three, return them
4. If neither of them is a multiple of three, start traversing the array till you find a multiple of three, and replace y with that number
5. Return the two numbers if a multiple of three was found

If the array can also have negative numbers, do the same thing but this time sort the array in increasing order, since the product of two negative numbers might be the answer.