Question: http://codility.com/demo/take-sample-test/max_product_of_three
Question Name: MaxProductOfThree
An small trap: multiplying two negatives makes a positive number.
1 2 3 | def solution(A): A.sort() return max(A[0]*A[1]*A[-1], A[-1]*A[-2]*A[-3]) |
UPDATE on 03-02-2015: Thanks to @Julian, there is an O(N) solution. We sort the input in the original solution, because we want the two minimum and three maximum elements. However, with bookkeeping, sorting is not necessary.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | // you can also use imports, for example: import java.util.Arrays; // you can use System.out.println for debugging purposes, e.g. // System.out.println("this is a debug message"); class Solution { public int solution(int[] A) { int[] maxes = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE}; // Invariant: maxes[0] <= maxes[1] <= maxes[2] int[] mins = {Integer.MAX_VALUE, Integer.MAX_VALUE}; // Invariant: mins[0] <= mins[1] // O(n) for( int a : A ) { updateMaxes( a, maxes ); updateMins( a, mins ); } System.out.println(Arrays.toString(maxes)); System.out.println(Arrays.toString(mins)); int obvious = maxes[0] * maxes[1] * maxes[2]; int twoBigNegs = mins[0] * mins[1] * maxes[2]; return Math.max( obvious, twoBigNegs ); } private static void updateMaxes( int a, int[] maxes ) { if( a >= maxes[2] ) { // Found new max, shift down maxes[0] = maxes[1]; maxes[1] = maxes[2]; maxes[2] = a; } else if( a >= maxes[1] ) { maxes[0] = maxes[1]; maxes[1] = a; } else if( a > maxes[0] ) { maxes[0] = a; } } private static void updateMins( int a, int[] mins ) { if( a <= mins[0] ) { // Found new min, shift down mins[1] = mins[0]; mins[0] = a; } else if( a < mins[1] ) { mins[1] = a; } } } |
The second solution is provided by @Julian.
I think it’s possible to do this in O(n), with a little bookkeeping…
https://codility.com/demo/results/demoW657UY-XZ5/
Yes, it is working perfect! Thanks for sharing your new solution!
Thanks for sharing this cool solution! Looks like codility mistakenly evaluate it as O(nlogn) rather than O(n)
Yes, you are right. Probably they did not notice the O(N) solution, which is not so general 🙂
It seems that it is impossible to distinguish between O (N) and O (N log N) in practice unless you impose a very drastic constant, but then the requirement is actually much stricter.
You could use a heap instead of sorting to get 3 max, and an inverse heap of the rest to get 2 min.
Good idea! Thanks!
How do you think of the perfect solutions? I can’t get the best performance even though I can get 100% accurate solutions. Any tips?
Please refer to my blog post.
Here is my C++ code:
Cannot pass Codility test. Please do test before posting. And please include all head files.
The line “A[P] * A[Q] * A[R] (0 less P less Q less R less N)” was really confusing since one can assume that R should be less then N, since they are saying about PRQ triplet, and not (A[P]*A[Q]*A[R]) triplet at first.
Here is my O(N) CPP solution, which somehow similar to a java code, but anyways, you don’t need to sort an array to find 5 elements.
Yes, sorting is not necessary, but makes the solution shorter.
Related to task description, I would expect that both solutions returns wrong values, or what do I miss here (because with sorting, I ignore the position in the original array completely, with second solution, the min-values might occur after the retrieved max value).
Part of task description
A non-empty zero-indexed array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).
However, codility says to both solutions 100%. Do they ignore their own posted condition here?
It is a bit tricky. Actually sorting is fine, because the order does not matter. Given any three valid and non-duplicate indexes (0<= P, Q, R < N and P != Q, Q != R, R != P), we can get one and only one arrangement, whose items are an increasing array. The only meaning of 0 ≤ P < Q < R < N is: P, Q and R are valid index; and P, Q and R are not duplicate.
Dear Sheng,
thanks for feedback. My understanding of P < Q < R is a bit different (for me it reads that P should be smaller than Q and Q should be smaller than R), which would mean that the values have to appear in this order. Funnily also the samples provided by Codility are manifesting this approach (Triplets (0,1,2), (1,2,4) and (2,4,5) ).
However, that would increase the difficulty level pretty much and wouldn´t fit to the "Painless" level, so probably my understanding is wrong (and maybe I should raise this question to Codility 🙂 ).
It is completely a mathematical language issue. Consider any three elements A, B, and C, there indexes are M, N, L.
One one hand, the product of them is same, no matter what order is taken: A * B * C = C * B * A = A * C * B = ……
On the other hand, because they are not duplicate (their indexes are different). M != N != L. We can make: P = min(M, N, L), Q = middle(M, N, L), R = max(M, N, L).
As a result, ANY three-element-arrangement is a candidate for the answer. The statement “0 ≤ P < Q < R < N" means nothing BUT these three elements should be different in index. There are some similar description in other Codility challenges. You need to get through its real definition. Otherwise, some of them are intractable. PS: in other words, in the question's example input, the product of triplet (2, 3, 5) is the same as (2, 5, 3) and (5, 3, 2). In all these three triplets, the P is 2, Q is 3, and R is 5. Actually the content of P, Q, and R does not matter at all. We can try (5, 3, 2) instead of (2, 3, 5), because they have the same product.
Thanks again for feedback. I think I got now my misunderstanding. I implicitly interpreted that P, Q and R are linked to the position in the array, but that is not mentioned, it is just defined for the triplet (and there indeed it doesn´t matter).
And good to know that I will face that more often in other Codility challenges :-).
C# solution
Technically, this is a fail. Because you are *replacing* the array with a new one – which requires you to use another array and throw away the input memory. An adaptation of your solution would be to use System.Array.Sort(A); which sorts A in place in O(n log n) time, and doesn’t create an extra array, and therefore satisfies the space complexity requirement. But otherwise, your solution is bang on. There are faster ways (the O(N) solution), but yours passes the test so who cares. It’s way more readable.
UPDATE #1: ignore my last. linq is smart enough to apply the sort in place, and ignore the ToArray() (simply casting the sorted source elements). So it doesn’t violate the spatial complexity
UPDATE #2: Ignore my last again! Linq is NOT applying the sort in place. it is in fact creating a new array. So this is technically a fail. You DO need to use something line Array.Sort(A) which is an in place sort
Yes, there is some space to improve the space complexity.
FYI, O(NlogN) and O(N) is definitely different. The problem for the OJ platform is that, they are so close that OJ platform cannot distinguish them with small testing cases.
Adding my verbose solution 100%:
I also was going to use bookkeeping but the requirements in terms of space says O(1) and I got a little bit confused, thinking that every array will be O(n) in space, but it’s cool how arrays with O(1) space can be used, thanks @Julian.
C++ 100% solution , O(NlogN):
I submitted my code which is basically merge sort and return like your Python code in two lines at the start of this page but it says performance is 80% only (Accuracy: 100%), can you comment on why that could be the case?
At least, your solution does not meet the space requirements: expected worst-case space complexity is O(1). The merge sorting needs O(N) space.
can someone tell me why we skipped index 3 ?
Because index 3 is never in the result three-element. There are three cases for the input numbers:
1. All positive; 2. all negative; 3. includes positive and negative. Think about the problem in each case and combine the result. Your will find out why.
that doesnt explain why we skipped index 3. This makes no sense. There is no explanation of why they chose (0, 1, 2), (1, 2, 4) and (2, 4, 5) in the example. Whats wrong with (0,1,3) for example
There is a mathematic proof. But I am too lazy to write it down:-) If you followed my suggestion (considering three cases), I would expect you got the right solution.
A quick correction: I am not skipping the 3rd items. After sorting, I skip all the items from the 3rd position to the 4th last position. For example, with sorted content [x0, x1, x2, x3, x4, x5, x6, x7], I ignored x2, x3, and x4.
100% , 100% Answer in java.
Nice solution!
I achieved 100% by myself, but I wasn’t satisfied. I noticed that sorting (which gives the nlogn complexity) is not even necessary, you just have to find the mins and maxes. So I looked it up with Google and this came up.
Btw, I searched for the 3 smallest and 3 biggest numbers and just combined them in a nested loop. Brute force yay! Turns out there is a more elegant way, thanks!
Thanks for your visiting! Enjoy coding!
Java solution, 100%. I don’t know if I am missing something.
You should have already covered all cases 🙂
Hi, i make some solution in Python but thinks that is more exact than main solution, if not, u can answer me why:
It’s too slow to pass the testing.
the initial sorted solution:
return max(A[0]*A[1]*A[-1], A[-1]*A[-2]*A[-3])
doesn’t pass the test: [-50, -45, -5, 4]; the max should be -50*-45*4 = 9000 but returns 900 (-45*-5*-4), so, if there are more than two negatives, and a single positive, you need to remove the third negative.
I did not see how could you get 900 with the my solution:
Your test case: [-50, -45, -5, 4]
Returned value: 9000
Apparently the solution will return 9000, because:
max(A[0]*A[1]*A[-1], A[-1]*A[-2]*A[-3])
= max(-50*-45*4 , -45*-5*-4)
= max(9000, 900)
= 9000
You adopted the bookkeeping solution from Julian. I didn’t get it at first, so I decided to do it in Python to figure it out. Here’s what I got. It’s tested and got 100%. I guess the space for the 2 and 3 length lists that hold the highest and lowest values still count at O(1).
This code raises an error.
This line dont look right:
elif a max[0]*min[0]*min[1]:
oops~ Patrick forgot to include the code into the “pre” section. The code is partially missing.
PS: I complete the code. It should work well now.
Java 100/1000:
can you explain your code?
# Following is my code, always keeping the maximum three and minimum two numbers.
# Why it gives some wrong answers? for large_random, it gives 999,000,000 while the
# expectation is 1,000,000,000
Your logic to compute the L is wrong. It should be:
Result: 100/100/100
https://app.codility.com/demo/results/training9EME9B-ZN7/
Please check.
pascal solution, with one pass of Array
Here is my solution. Got 100/100 with C#
https://app.codility.com/demo/results/training6ZZESS-BBA
Hi Sheng,
I am referring to the solution using sorting.
Assume that if we have the array – A, such that the maximum element is repeated more than once, then in that case,: A[-1] = A[-2].
However, the question says : P < Q < R.
So, we have to find the maximum 3 elements that are not repeating?
PS: Same is true with the minimum elements if there are negative number. We have to find the Minimum non repeating elements ?
Thanks
Srikanth
The condition “P < Q < R" is intentionally misleading. (?) It does NOT matter at all. The only thing "P < Q < R" says is these three numbers come from three DIFFERENT index. PS: P, Q, and R are index, not the number. Order? Does not matter. For example, the product of triplet (2, 4, 5) = the product of triplet (4, 5, 2) = the product of triplet (5, 4, 2).
100% Python solution. Hi @Sheng, I tried solving it without using sorting. Just min and max. I believe my complexity is O(N), but Codility shows O(N*logN). Could you please comment regarding time complexity? Thanks.