You are given an array arr which consists of only zeros and ones, divide the array into three 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 &lt; j, such that:


	arr[0], arr[1], ..., arr[i] is the first part,
	arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part, and
	arr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part.
	All three parts have equal binary values.


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.

&nbsp;
Example 1:
Input: arr = [1,0,1,0,1]
Output: [0,3]
Example 2:
Input: arr = [1,1,0,1,1]
Output: [-1,-1]
Example 3:
Input: arr = [1,1,0,0,1]
Output: [0,2]

&nbsp;
Constraints:


	3 &lt;= arr.length &lt;= 3 * 104
	arr[i] is 0 or 1


class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        n = len(arr)
        count_one = arr.count(1)
        if count_one == 0: return [0,n-1]
        if count_one % 3!= 0: return [-1,-1]
        target_ones = count_one // 3
        breaks = []
        one_count = 0
        for i , bit in enumerate(arr):
            if bit ==1 :
                one_count +=1
                if one_count in [1,target_ones+1,2*target_ones+1]:breaks.append(i)   
                if one_count in [target_ones,2*target_ones,3*target_ones]:breaks.append(i)
        i1,j1,i2,j2,i3,j3 = breaks
        
        if not arr[i1:j1+1] == arr[i2:j2+1] == arr[i3:j3+1]:return [-1,-1]
        
        trailing_zeroes_left  = i2 - j1 - 1
        trailing_zeroes_mid   = i3 - j2 - 1
        trailing_zeroes_right = n -  j3 - 1
        if trailing_zeroes_right > min(trailing_zeroes_left,trailing_zeroes_mid):return [-1,-1]
        j1 += trailing_zeroes_right
        j2 += trailing_zeroes_right
        return [j1,j2+1]
    
class Solution {
    public int[] threeEqualParts(int[] arr) {
        List<Integer> ones = new ArrayList<>();
        for (int i = 0; i < arr.length; i++){
            if (arr[i]==1){
                ones.add(i);
            }
        }
        if (ones.size()==0){ // edge case
            return new int[]{0,2};
        }
        int[] ans = new int[2];
        int each = ones.size()/3;
        for (int i = 0; i < 2 && ones.size()%3==0; i++){ // for the first 2 partitions
            for (int j = 0; j < each-1; j++){ // compare gaps
                if (ones.get(j+1+i*each)-ones.get(j+i*each)!=ones.get(j+2*each+1)-ones.get(j+2*each))
                    return new int[]{-1, -1};
            }
            ans[i]=ones.get((i+1)*each-1)+i+(arr.length - 1 - ones.get(ones.size()-1)); // cut point
        }
        return ones.size()%3>0||ans[0]>=ones.get(each)||ans[1]>ones.get(2*each)?
            new int[]{-1, -1} : ans;
    }
}
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& v) {
        vector<int> one;
        int n=v.size();
        for(int i=0;i<n;i++){
            if(v[i]==1) one.push_back(i+1);
        }
        if(one.size()==0){
            return {0,2};
        }
        if(one.size()%3)    return {-1,-1};

        int ext=n-one.back(),sz=one.size();
        int gap1=one[sz/3]-one[sz/3-1]-1,gap2=one[2*sz/3]-one[2*sz/3-1]-1;
        // cout<<gap1<<" "<<gap2<<endl;
        if(gap1<ext || gap2<ext)    return {-1,-1};

        string s1,s2,s3;
        for(int i=0;i<=one[sz/3-1]+ext-1;i++){
            if(s1.length()>0 || v[i])   s1+=to_string(v[i]);
        }

        for(int i=one[sz/3-1]+ext;i<=one[2*sz/3-1]+ext-1;i++){
            if(s2.length()>0 || v[i])   s2+=to_string(v[i]);
        }

        for(int i=one[2*sz/3-1]+ext;i<=n-1;i++){
            if(s3.length()>0 || v[i])   s3+=to_string(v[i]);
        }
        //All 3 Numbers in vector v :-
        // num1={0,one[sz/3-1]+ext-1};
        // num2={one[sz/3-1]+ext,one[2*sz/3-1]+ext-1}
        // num3={one[2*sz/3-1]+ext,n-1};
        if(s1==s2 && s2==s3)    return {one[sz/3-1]+ext-1,one[2*sz/3-1]+ext};
        return {-1,-1};
    }
};
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var threeEqualParts = function(arr) {
  const ones = arr.reduce((s, n) => s + n, 0);
  if (ones === 0) return [0, 2];
  if (ones % 3 !== 0) return [-1, -1];
  let onesToFind = ones / 3;
  let k = arr.length;
  while (onesToFind > 0) if (arr[--k] === 1) --onesToFind;
  const iter = arr.length - k;
  const firstOne = arr.indexOf(1);
  const secondOne = arr.indexOf(1, firstOne + iter);
  for (let i = 0; i < iter; i++)
    if (arr[i + firstOne] !== arr[k + i] || arr[i + secondOne] !== arr[k + i]) return [-1, -1];
  return [firstOne + iter - 1, secondOne + iter];
};
Three Equal Parts