The task was given an array of integers, find the maximum product between two numbers from the array, that is a multiple of 3.
</script>
arr = [-9, -11, 4, 6, 9, 7];
arr2 = [-11, 4, 6, 7];
arr3 = [11, 3, 5]
function findProduct(arr) {
let maxProduct = 0;
for(let i = 0; i < arr.length - 1; i ) {
for(let j = i 1; j < arr.length; j ) {
let product = arr[i] * arr[j]
if(product % 3 !== 0) continue;
if(product > maxProduct) {
maxProduct = product
}
}
}
return maxProduct
}
console.log(findProduct(arr))
console.log(findProduct(arr2))
console.log(findProduct(arr3))
</script>
´´´´
CodePudding user response:
An O(N)
time, O(1)
extra space algorithm:
- Traverse the array, keep track of two variables:
max_multiple_of_three
andmin_multiple_of_three
- Traverse the array, keep track of two variables:
largest_number_in_array
(which shouldn't have the same index asmax_multiple of three
) andsmallest_number_in_array
(which shouldn't have same index asmin_multiple_of_three
) - The answer will be either
max_multiple_of_three * largest_number_in_array
ormin_multiple_of_three * smallest_number_in_array
Example 1:
arr = [-9, -11, 4, 6, 9, 7]
max_multiple_of_three = 9
min_multiple_of_three = -9
largest_number_in_array = 7
smallest_number_in_array = -11
ans = max(-9*-11, 9*7) = 99
Example 2:
arr = [-11, 4, 6, 7]
max_multiple_of_three = 6
min_multiple_of_three = 6
largest_number_in_array = 7
smallest_number_in_array = -11
ans = max(6*-11, 6*7) = 42