'Finding numbers with largest multiplication result in a single O(n) pass through an array
Question: given an array, you need to find 3 elements inside the array that will give the biggest product of all when multiplied.
For example, given the following input:
-4, 1, -8, 9, 6
...the expected output is -4, -8, 9, as -4 * -8 * 9 == 288.
you can assume that there are no nulls inside the array.
signature must be public static int findTriplet(int[] a);.
my code:
public static int findTriplet(int[] a) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE,
maxLowby2 = Integer.MIN_VALUE, maxLowby1 = Integer.MIN_VALUE,
secondMin = Integer.MAX_VALUE, minIndex = -1, maxIndex = -1, indexofLowby1 = -1;
//we run a for loop to go over the array and collect all our needed information.
for (int i = 0; i < a.length; i++) {
//first we find the smallest value
if (min > a[i] && a[i] < 0) {
min = a[i];
minIndex = i;// we save the index so we can find other num that is negative and is different from this 1
////here we try to find the second smallest num in the array in such that it has to be a minus otherwise we wont be able to get a popsitive number(-1*-1=positive)
//if the index is different and second Min is smaller then the value in a[i] and a[i] must be a negetive num;
} else if (minIndex != i && secondMin > a[i] && a[i] < 0) {
secondMin = a[i];
}
//
if (max < a[i]) {
max = a[i];
maxIndex = i;
//now we look for only positive numbers
//here we need to find two other sumbers that are the biggest in the array but are different then each other.
} else if (max > a[i] && a[i] >= 0 && maxLowby1 < a[i] && maxIndex != i) {
maxLowby1 = a[i];
indexofLowby1 = i;
//here we find the last positive number that will be smaller the max and maxlowBy1
} else if (a[i] >= 0 && indexofLowby1 != i)
maxLowby2 = a[i];
}
// we creat the needed numbers and return the max value of them.
int finalMax = max * maxLowby2 * maxLowby1;
int secondMinus = max * min * secondMin;
return Math.max(finalMax, secondMinus);
} ```
Solution 1:[1]
If you only need to keep track of three values it's pretty easy to avoid inner loops. Keep track of the positives and negatives separately. You'll only need to keep track of the two smallest negatives.
Compare each new number against the previously known values. By falling through you determine where to slide values down (in terms of absolute value) and insert the new one.
The special case of three values is treated distinctly. All three initial values are captured separately and only used in this instance. This does assume there are at least three values in the list.
n1 = n2 = p1 = p2 = p3 = 0; // negatives / positives with largest abs()
m3 = m2 = m1 = int.minValue; // store for case when only three values
for(i = 0; i < a.length; i++) {
m = a[i];
if (m > p3) { p1 = p2; p2 = p3; p3 = m; }
else if (m > p2) { p1 = p2; p2 = m; }
else if (m > p1) { p1 = m; }
else if (m < n2) { n1 = n2; n2 = m; }
else if (m < n1) { n1 = m; }
switch (i)
case 1 : m1 = m; break;
case 2 : m2 = m; break;
case 3 : m3 = m; break;
}
l = a.length;
if (l < 3) { v = 0; } // error?
else if (l == 3) { v = m1 * m2 * m3; }
else if (n1 * n2 > p1 * p2) { v = n1 * n2 * p3; }
else { v = p1 * p2 * p3; }
return v;
Consider it to be pseudocode rather than proper Java.
https://www.online-python.com/Hreut5EWav
Below is essentially QuinncyJones's more compact logic but without the sort operation. And I reduced the number of variables involved aseell.:
n1 = n2 = 0; // two smallest negatives
m3 = m2 = m1 = int.minValue; // three largest values regardless of sign
for(i = 0; i < a.length; i++) {
m = a[i];
if (m > m3) { m1 = m2; m2 = p3; m3 = m; }
else if (m > m2) { m1 = m2; m2 = m; }
else if (m > m1) { m1 = m; }
if (m < n2) { n1 = n2; n2 = m; }
else if (m < n1) { n1 = m; }
}
return m3 < 0 || n1 == 0 || n1 * n2 < m1 * m2 ?
m1 * m2 * m3 : n1 * n2 * m3;
Solution 2:[2]
You can use:
import java.util.Arrays;
public class LargestMultiple {
private static void storeValues(
int new_value,
int[] values
)
{
int i = -1;
for (;i + 1 < values.length && new_value > values[i+1]; ++i){}
if (i >= 0)
{
for (int j = 0; j < i; ++j)
{
values[j] = values[j+1];
}
values[i] = new_value;
}
}
public static int findTriplet(
int[] a
)
{
if (a.length == 0)
{
throw new IllegalArgumentException("Not enough values");
}
if (a.length <= 3)
{
int value = a[0];
for (int i = 1; i < a.length; ++i)
{
value *= a[i];
}
return value;
}
int[] maximums = {0, 0, 0};
int[] minimums = {0, 0};
int[] negatives = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
int num_positive = 0;
for (int i = 0; i < a.length; i++)
{
if (a[i] < 0)
{
storeValues(-a[i], minimums);
storeValues(a[i], negatives);
}
else
{
storeValues(a[i], maximums);
num_positive++;
}
}
if (num_positive > 0)
{
return Math.max(
minimums[0] * minimums[1],
maximums[0] * maximums[1]
) * maximums[2];
}
else
{
return negatives[0] * negatives[1] * negatives[2];
}
}
public static void test(final int[] values)
{
System.out.println(
Arrays.toString(values)
+ " -> "
+ findTriplet(values)
);
}
public static void main(final String[] args)
{
test(new int[]{1});
test(new int[]{1, 2});
test(new int[]{1, 2, 3});
test(new int[]{1, 2, 3, 4});
test(new int[]{1, 2, -1, -2});
test(new int[]{1, 2, -1});
test(new int[]{1, 2, 3, -1});
test(new int[]{1, 2, 3, -1, -4});
test(new int[]{-1, -2, -3, -4});
}
}
Which outputs:
[1] -> 1 [1, 2] -> 2 [1, 2, 3] -> 6 [1, 2, 3, 4] -> 24 [1, 2, -1, -2] -> 4 [1, 2, -1] -> -2 [1, 2, 3, -1] -> 6 [1, 2, 3, -1, -4] -> 12 [-1, -2, -3, -4] -> -6
Note: Although storeValues is O(N) on the size of the array, it is always called from findTriplet with fixed-sized arrays then, from within that function, it will have a constant O(1) execution time.
Solution 3:[3]
The result is always the product of the 3 highest numbers or of the highest and the 2 lowest numbers. So the 2 lowest and the 3 highest numbers have to be found. An O(n) solution is therefore possible since this can be done in one loop pass.
public static int findTriplet(int[] a) {
if(a.length < 3) throw new IllegalArgumentException("The array must have a length of at least 3!");
int[] n = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE };
for(int i : a) {
// find two lowest
if(i < n[0]) { n[1] = n[0]; n[0] = i; }
else if (i < n[1]) n[1] = i;
// find three highest
if(i > n[4]) { n[2] = n[3]; n[3] = n[4]; n[4] = i; }
else if(i > n[3]) { n[2] = n[3]; n[3] = i; }
else if(i > n[2]) n[2] = i;
}
int case1 = n[0] * n[1];
int case2 = n[2] * n[3];
return n[4] * (case1 > case2 ? case1 : case2);
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | |
| Solution 2 | MT0 |
| Solution 3 |