CODEWITHSUNDEEP
arraysalgorithmsortinginteger
mlila_p
mlila_p

Reputation: 131

In an array of numbers find higest product with specific multiple

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

Upvotes: 0

Views: 82

Answers (1)

Abhinav Mathur
Abhinav Mathur

Reputation: 8196

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 have the same index as max_multiple of three) and smallest_number_in_array (which shouldn't have same index as 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

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

Upvotes: 1

Related Questions