# [LeetCode 927. Three Equal Parts](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/610/week-3-july-15th-july-21st/3817/)
### Daily challenge Jul 17, 2021 (HARD)

>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 < 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.

:::info
**Example 1:**
**Input:** arr = [1,0,1,0,1]
**Output:** [0,3]
:::

:::info
**Example 2:**
**Input:** arr = [1,1,0,1,1]
**Output:** [-1,-1]
:::

:::info
**Example 3:**
**Input:** arr = [1,1,0,0,1]
**Output:** [0,2]
:::

:::warning
**Constraints:**
* 3 <= arr.length <= 3 * 104
* arr[i] is 0 or 1
:::

---

### Approach 1 : :bulb: + :book:
**`40 ms ( 63.25% )`** **`O(N)`**

將 `arr` 中 `1` 出現的 index 存入 vector.
出現次數 `numberOfOne = vector.size()`.
* `numberOfOne == 0` ---> return **`{0, arr.size()}`**.
* `numberOfOne % 3 != 0` ( `1` 無法平均分配到各個 GROUP ) ---> return **`{-1, -1}`**.
* `numberOfOne % 3 == 0` ---> TRY VALID PARTITION.

**1.** 因為 `1` 需要平均分配到各個 GROUP ( 皆有 `dif = numberOfOne / 3` 個 `1` )，可以先分配每組`最高位的 1` ( **`group{index[0], index[dif], index[2*dif]}`** )，再逐個進行判斷。

| arr | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | NULL |
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| **GROUP** | | | **[0]** | | | **[1]** | | | **[2]** | | | |

**2.** 進行判斷 :
>* 是否仍在範圍內 ---> **`group[2] < size`**.
>* 三組是否相同 ---> **`arr[group[0]] == arr[group[1]] && arr[group[1]] == arr[group[2]`**.
>* 各組 index **`+1`**.

| arr | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | NULL |
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| **GROUP** | | | | **[0]** | | | **[1]** | | | **[2]** | | |

**3.** 重複 **`2.`** 的步驟.

| arr | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | NULL |
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| **GROUP** | | | | | **[0]** | | | **[1]** | | | **[2]** | |

**4.** **`group[2] == size`** ---> END LOOP

| arr | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | NULL |
| :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: | :--------: |
| **GROUP** | | | | | | **[0]** | | | **[1]** | | | **[2]** |

>* 若 **`group[2] == size`** ( GOT THE ANSWER ) ---> return **`{group[0] - 1, group[1]}`**.
>* 否則 return **`{-1, -1}`**.

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int size = arr.size();
        vector<int> index;
        
        // count 1
        for(int i=0; i<size; i++){
            if(arr[i] == 1) index.push_back(i);
        }
        
        int numberOfOne = index.size();
        if(numberOfOne % 3 != 0)  return vector<int>({-1, -1});
        if(numberOfOne == 0)    return vector<int>({0, size-1});
        
        int dif = numberOfOne / 3;
        int group[3] = {index[0], index[dif], index[2*dif]};    // each group's first 1
        while(group[2] < size && arr[group[0]] == arr[group[1]] && arr[group[1]] == arr[group[2]]){
            for(int j=0; j<3; j++){
                group[j]++;
            }
        }
        
        if(group[2] == size)    return vector<int>({group[0]-1, group[1]});
        return vector<int>({-1, -1}); 
    }
};