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

 

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 * 104
  • arr[i] is 0 or 1

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]
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,0,1,0,1]

Output

x
+
cmd
[0,3]

#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]
Copy The Code & Try With Live Editor

Input

x
+
cmd
arr = [1,0,1,0,1]

Output

x
+
cmd
[0,3]
Advertisements

Demonstration


Previous
#926 Leetcode Flip String to Monotone Increasing Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#928 Leetcode Minimize Malware Spread II Solution in C, C++, Java, JavaScript, Python, C# Leetcode