Algorithm
Problem Name: 927. Three Equal Parts
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, andarr[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.
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]
Constraints:
3 <= arr.length <= 3 * 104arr[i]is0or1
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const threeEqualParts = function (A) {
let countNumberOfOnes = 0
for (let c of A) if (c === 1) countNumberOfOnes++
if (countNumberOfOnes === 0) return [0, A.length - 1]
if (countNumberOfOnes % 3 != 0) return [-1, -1]
const k = countNumberOfOnes / 3
let i
// find the first 1 in the array
for (i = 0; i < A.length; i++) if (A[i] == 1) break
let start = i
// find (k+1)th 1 in the array
let count1 = 0
for (i = 0; i < A.length; i++) {
if (A[i] == 1) count1++
if (count1 == k + 1) break
}
let mid = i
//find (2*k +1)th 1 in the array
count1 = 0
for (i = 0; i < A.length; i++) {
if (A[i] === 1) count1++
if (count1 === 2 * k + 1) break
}
let end = i
// Match all values till the end of the array
while (end < A.length && A[start] === A[mid] && A[mid] === A[end]) {
start++
mid++
end++
}
// Return appropriate values if all the values have matched till the end
if (end == A.length) return [start - 1, mid]
// otherwise, no such indices found
return [-1, -1]
}
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
class Solution(object):
def threeEqualParts(self, A):
sm = sum(A)
if sm % 3: return [-1, -1]
t = sm // 3
if not t: return [0, len(A) - 1]
breaks = [0] + [i for i, x in enumerate(A) if x]
i1, j1, i2, j2, i3, j3 = breaks[1], breaks[t], breaks[t + 1], breaks[2 * t], breaks[2 * t + 1], breaks[3 * t]
if not (A[i1: j1 + 1] == A[i2: j2 + 1] == A[i3: j3 + 1]): return [-1, -1]
if i2 - j1 < len(A) - j3 or i3 - j2 < len(A) - j3: return [-1, -1]
return [j1 + len(A) - j3 - 1, j2+ len(A) - j3]
Input
Output