# Leetcode: Three Equal Parts

Three Equal Parts

<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/three-equal-parts“><img align=”right” width=”200″ height=”183″ src=”” /></a>

Similar Problems:

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[1], A[2], …, 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:

1. 3 <= A.length <= 30000
2. A[i] `= 0 or A[i] =` 1

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/three-equal-parts
// Basic Ideas: Find the value from the last part
// Complexity: Time O(n), Space O(1)
func threeEqualParts(A []int) []int {
count := 0
for _, v := range A {
if v == 1 { count++ }
}
if count%3 != 0 {
return []int{-1, -1}
}

if count == 0 {
return []int{0, 2}
}

c := 0
index1, index2, index3 := -1, -1, -1
for i, v := range A {
if v == 1 { c++ }
if index1 == -1 && c == 1 {
index1 = i
}
if index2 == -1 && c == count/3+1 {
index2 = i
}
if index3 == -1 && c == 2*count/3+1 {
index3 = i
}
}
for i := 0; i<len(A)-index3; i++ {
i1, i2, i3 := index1+i, index2+i, index3+i
if i1 >= index2 || i2>=index3 || A[i1] != A[i3] || A[i2] != A[i3] {
return []int{-1, -1}
}
}
return []int{index1+len(A)-1-index3, index2+len(A)-index3}
}
```

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”” alt=”slack”/></a></div>

</div>

Footnotes:

[1]