def woodCut(arr, k):
    """
    arr: array of integer denoting lengths of wood
    k: required number of uniform cut

    Note that not every element needs to be cut.
    If k = 1, simply return the largest.

            lr
    OOOOO...OOXX...XXX
             lr
    Complexity O(N + LogM), N = len(arr), M = max(arr)

    Thought process: change length, see how many equal pieces can get
    """

    l, r = 0, max(arr)

    # compute how many pieces of length x we can cut
    count = lambda arr, x: sum(a // x for a in arr)

    while l + 1 < r:
        m = (r - l) // 2 + l
        if count(arr, m) == k:
            l = m
        elif count(arr, m) < k:
            # cut size too big
            r = m - 1
        else:
            # cut size too small
            # cannot add, or l may point to X
            l = m
    if count(arr, r) == k:
        return r
    elif count(arr, l) == k:
        return l
    return 0