# Return the largest product of 2 numbers that is a multiple of 9 in O(n)

Given an array of integers, I have to return the largest product of any 2 numbers, and that product has to be a multiple of 9.

Example input 1:
int[] a = {6, 5, 7, 2, 4, 8, 9};
Example output:
72

Example input 2:
int[] b = {1, 6, 7, 3};
Example output:
18


This is easy with 2 nested loops, calculating all products between every element of the array and checking if the product is a multiple of 9, but that solution is $O(n^2)$. I was told I can solve this problem in $O(n)$ only, but I'm struggling to cover all the cases.

I have the following code:

    int max_number = -1;
int max_multiple_9 = -1;

for(int i = 0; i < input.length; i++) {
if(input[i] % 9 == 0) {
if(input[i] > max_multiple_9) max_multiple_9 = input[i];
else if(input[i] > max_number) max_number = input[i];
} else {
if(input[i] > max_number) max_number = input[i];
}
}

return max_multiple_9*max_number;


This only works for cases where there is a multiple of 9 in the array (like the first example), because I'm looking for the greatest multiple of 9 and multiplying it for the greatest any other number. But how would I change the code to also find products that don't involve multiples of 9, such as 6*3 in the second example?

The solution will be of one of two forms :

a * b where a is divisible by 9

or

c * d where c is divisible by 3 and d is divisible by 3

To find the maximum of the first from we need to find the greatest number divisible by 9, and combine it with the greatest number, or the second greatest if the one divisible by 9 is the greatest.

To find the maximum of the second form we need to find the two greatest numbers divisible by 3.

So you can loop all numbers and determine for each number if it is a better candidate for a,b, c or d.

After that loop, calculate a*b and c*d, and the greatest of both wins, and is the result.

This algorithm results in $O(n)$ complexity.

• I actually thought about the 2nd possible scenario but was trying to combine the 2 scenarios in some fancy formula. Doing them both at the sime time independently and in the end choosing the greatest of the 2 sounds so simple that I can't believe I didn't think of it first. Thank you so much – Mr. Phil Nov 7 '17 at 19:30