# Solution to Min-Max-Division by codility

6 Apr

Question Name: Min-Max-Division or MinMaxDivision

Logically, it seems to be similar with the boron2013 (Flags) challenge by Codility. And the following is my Python solution.

UPDATE – 2014/09/19: thanks to Martin Kysel. The function signature is changed to:
def solution(K, M, A):
Don’t be confused by the new parameter M. Ignore the M, use the original solution, and you will pass all the test.

In addition, thanks to @Guillermo (StackOverflow Profile), here is the C++ solution from @Guillermo, which inspired me. Thanks again for his sharing!

### 16 Replies to “Solution to Min-Max-Division by codility”

1. wongiseng says:

Java solution, greedy checking :

• Sheng says:

Thanks for sharing your solution. If it was with some key comments, it would be more helpful.

• Sheng says:

I am sorry. Everytime I access your website with Firefox, the page makes FF die. I have to remove it for security consideration for my visitors.

• Martin Kysel says:

They introduced M to confuse us! 😀

Your implementation is correct, I made false assumptions when porting it!

• Sheng says:

That is fine. And thank for telling me the change to the function signature.

I will add some explanation to help the others to understand the solutions.

2. I’m confused regarding the time complexity. Why is the time complexity O(N*log(N+M)) instead of O(N*log(N*M))? The upper bound of the binary search is equal to the sum of the elements in A, which is at most N*M.

• Sheng says:

Yes, you are right. The complexity is not exactly O(N*log(N+M)). O(N*log(N*M)) = O(N*(log(N) + log(M))). Therefore, when N is close to M, O(N*log(N*M)) is the same as O(N*log(N+M)). In generaly case, I do not know the answer.

• Yixuan Wang says:

“when N is close to M, O(N*log(N*M)) is the same as O(N*log(N+M))”
this seems wrong…

3. Hazem Farouk says:

Thank you very much for your solution. Really enlightening 🙂

Here’s the Java version of your Python solution:

4. Raf says:

What is throwing me off is that the exercise is asking for “expected worst-case time complexity is O(N*log(N+M))”

If I’m reading your solution correctly you’re first looping through all the elements followed by the binary search section. Isn’t that O(n) + log(n+m) ?

• Sheng says:

You are partly right. The binary search at #37 is inside the while loop around #35: so the complexity is O(N) * O(log(N+M)) = O(N*log(N+M)).

5. micropentium6 says:

I was tricked by M…”no greater than M” made me made the assumption that the largest element in the array must be M, which is not true, well, at least in Codility test cases. I got 43% just because of failing to recognize this “fact”…
If we consider the smallest max as a monotonic sequence, the lower bound of the sequence is the largest element in the array, and the higher bound is the sum of all elements. Then we choose the possible “smallest max” at the middle of the sequence and always greedily drops half of of the sequence by comparing the number of partitions based upon current “smallest max” with the proposed K. If our partition L is less than K, we probably can find a even smaller “smallest max” by dropping the lager half of the sequence, otherwise, drop the smaller half…

• Sheng says:

Agree that the parameter M is misleading.

6. Sailingfish says:

M is not misleading. In fact it can be proved that the result is between (mean，mean+M).

Updated by Sailingfish on Aug 19, 2017.

7. Boshu says:

The initial lower bound could be max( sum(A)/K, max(A) )