Lesson 12: MinMaxDivision (Min Max Division)

Lesson 12: MinMaxDivision
https://codility.com/programmers/lessons/12

This is a simple binary search problem.

#include <alloca.h>

int check(int num, int K, int* A, int N)
{
    int i = 0;
    
    int sum = 0;
    while (i < N){    
        //indeed, we don't need below because the lower limit is max(A).
        if (A[i] > num){
            return 0;
        }
        sum += A[i];
        if (sum > num){
            sum = A[i];

            K--;
            if (K == 0){
                return 0;
            }
        }
        i++;
    }
    
    return 1;
}

int solution(int K, int M, int A[], int N) 
{
    int max = A[0];
    int sum = 0;
    
    int i;
    for (i = 0; i < N; i++){
        max = max < A[i] ? A[i] : max;
        sum += A[i];
    }
    
    int beg = max;
    int end = sum; 
    
    int min = sum; 
    while (beg <= end){
        int mid = (beg + end) / 2;
        if (check(mid, K, A, N)){
            min = mid;
            end = mid - 1;
        }
        else {
            beg = mid + 1;
        }
    }
    
    return min;
}

NOTE: I was thinking if this is a solution with the O(N * log(N + M)) time complexity, since the upper bound for the binary search will be N * M (when all the values in the array are M, the max = N * M). So the above code is indeed of the O(N * log (N * M)) time complexity.

This webpage explains the reason: http://blog.csdn.net/caopengcs/article/details/41834173

Since log(N * M) = log N + log M,
O(log(N*M)) = O(log N + log M)

As log N + log M is smaller than or equal to 2 * log(max(N, M)), it can be said that O(log N + log M) <= O(2 * log(max(N, M)))

Because max(M, N) is smaller than N + M, it can be said that
O(2 * log(max(N, M))) < O(2 * log(N + M))

And we can always remove any constant value from the big O notation, 
now we have got the O(log(N + M)) time complexity for the binary search part of the above code.

So