# Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the
# same binary value.
#
# If it is possible, return any [i, j] with i+1 < j, such that:
#
# A[0], A[1], ..., A[i] is the first part;
# A[i+1], A[i+2], ..., A[j-1] is the second part, and
# A[j], A[j+1], ..., A[A.length - 1] is the third part.
# All three parts have equal binary value.
# If it is not possible, return [-1, -1].
#
# Note that the entire part is used when considering what binary value it represents.  For example, [1,1,
# 0] represents 6 in decimal, not 3.  Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.
#
#
#
# Example 1:
#
# Input: [1,0,1,0,1]
# Output: [0,3]
# Example 2:
#
# Input: [1,1,0,1,1]
# Output: [-1,-1]
#
#
# Note:
#
# 3 <= A.length <= 30000
# A[i] == 0 or A[i] == 1
import collections


class Solution:
    def threeEqualParts_tle(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """

        # if 3 parts are equal, then start from the right, they have the same numbe of 1s starting from same position
        def find_first_one(start, end):
            for k in xrange(start, end, -1):
                if A[k]:
                    return k

        def get_value(start, end):
            res = 0
            for k in reversed(xrange(start, end)):
                res += (1 << (end - 1 - k)) if A[k] else 0
            return res

        l = len(A)
        i = l - 1
        while i >= 2:
            for j in xrange(i - 1, 0, -1):
                if get_value(i, l) == get_value(j, i) == get_value(0, j):
                    return [j - 1, i]

            i -= 1
        return [-1, -1]
        # j = i-2  # [0,j-1],[j,i-1],[i,l-1]
        # if get_value(i,l) == get_value(j,i) and get_value(j,i) == get_value(0,j):
        #     return [j,i]
        #
        # if get_value(i,l) < get_value(j,i):
        #     while i >= 2 and j >=1 and i-j >= 1 and get_value(i,l) < get_value(j,i):
        #         if A[i-1] == 0:
        #             i -= 1
        #         else:
        #             j -= 1
        #
        #
        #     if get_value(i,l) == get_value(j,i) and get_value(j,i) == get_value(0,j):
        #         return [i,j]
        #
        # else:

    def threeEqualParts_tle2(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """

        def get_value(start, end):
            res = 0
            for k in reversed(xrange(start, end)):
                res += (1 << (end - 1 - k)) if A[k] else 0
            return res

        l = len(A)
        i, j = l - 1, 1
        while j < i:
        # [0,j-1],[j,i-1],[i,l-1]
        if get_value(i, l) == get_value(j, i) == get_value(0, j):
            return [j - 1, i]

        if get_value(0, j) < get_value(i, l):
            j += 1

        elif get_value(0, j) > get_value(i, l):
            i -= 1

        elif get_value(0, j) == get_value(i, l):
            if A[i - 1] == 0:
                i -= 1
            elif A[i - 1] == A[j] == 1:
                i, j = i - 1, j + 1
            else:
                i -= 1
        else:
                i -= 1  # break the balance

        print i, j

        return [-1, -1]

    def threeEqualParts(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        ones, wrong = collections.Counter(A)[1], [-1, -1]

        if ones % 3:  # if number of 1's not appear 3x times, then it is wrong:
            return wrong

        # case [0,0,0,0,0]
        # bugfixed
        if not ones:
            return [0, len(A) - 1]

        one_number = ones / 3
        t, indexs = 0, []

        for k, v in enumerate(A):
            if v:
                t += 1
                # bugfixed, this should inside the first if check
                if t in {1, one_number + 1, 2 * one_number + 1}:
                    indexs.append(k)
                # bugfixed should be if instead of elif , see the case[1,1,0,0,1]
                if t in {one_number, 2 * one_number, 3 * one_number}:
                    indexs.append(k)

        # it breaks 3 part 0,0,0,..[i1,j1],0,0...[i2,j2],0,0..[i3,j3],0,0,..
        i1, j1, i2, j2, i3, j3 = indexs

        if not A[i1: j1 + 1] == A[i2:j2 + 1] == A[i3: j3 + 1]:
            return wrong

        # count 0 between j1,i2, j2,i3, j3, len(A)-1
        zero1, zero2, zero3 = i2 - j1 - 1, i3 - j2 - 1, len(A) - j3 - 1
        # for example 001100 1100 110000, you will not be able to break them even
        if zero1 < zero3 or zero2 < zero3:
            return wrong
        else:
            # for ex,  0011(j1) 00 0011(j2) 00 0011(j3)00
            # you can make it 001100 | 001100 | 001100
            # which means, we aleady know each part has 2 1's, the third part has 2 tail 0's
            # we also knows the first , second part has more tail 0's then the third
            # then we cna move the first , second right side 2 steps, to append 2 additional 0's
            # then we can get the equal 3 parts
            j1, j2 = j1 + zero3, j2 + zero3

            return [j1, j2 + 1]


if __name__ == '__main__':
    print Solution().threeEqualParts([0, 1, 0, 1, 1, 0, 1, 1, 0, 1])
    print Solution().threeEqualParts([1, 1, 0, 0, 1])
    print Solution().threeEqualParts([0, 1, 1, 0, 0, 1, 1, 1, 1, 1])
    print Solution().threeEqualParts([1, 0, 1, 0, 1])
    print Solution().threeEqualParts([1, 1, 0, 1, 1])
    print Solution().threeEqualParts(
        [1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1,
         1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0,
         0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0,
         1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1,
         1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1,
         0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1,
         1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1,
         1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1,
         0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1,
         0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0,
         0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0,
         0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1,
         1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0,
         1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0])
