Three Equal Parts
Problem
You are given an array arr of 0s and 1s. Divide the array into three non-empty parts so that all of these parts represent the same binary value. Return any [i, j] with i + 1 < j such that arr[0..i] is the first part, arr[i+1..j-1] is the second part, and arr[j..n-1] is the third part, and all three parts represent the same binary value. If it is not possible, return [-1, -1].
arr = [1, 0, 1, 0, 1][0, 3]def three_equal_parts(arr):
total = sum(arr)
if total % 3 != 0:
return [-1, -1]
if total == 0:
return [0, len(arr) - 1]
k = total // 3
n = len(arr)
ones = [i for i, v in enumerate(arr) if v == 1]
s1, s2, s3 = ones[0], ones[k], ones[2 * k]
length = n - s3
if s1 + length > s2 or s2 + length > s3:
return [-1, -1]
for d in range(length):
if arr[s1 + d] != arr[s2 + d] or arr[s2 + d] != arr[s3 + d]:
return [-1, -1]
return [s1 + length - 1, s2 + length]function threeEqualParts(arr) {
const total = arr.reduce((a, b) => a + b, 0);
if (total % 3 !== 0) return [-1, -1];
if (total === 0) return [0, arr.length - 1];
const k = total / 3, n = arr.length;
const ones = [];
for (let i = 0; i < n; i++) if (arr[i] === 1) ones.push(i);
const s1 = ones[0], s2 = ones[k], s3 = ones[2 * k];
const length = n - s3;
if (s1 + length > s2 || s2 + length > s3) return [-1, -1];
for (let d = 0; d < length; d++) {
if (arr[s1 + d] !== arr[s2 + d] || arr[s2 + d] !== arr[s3 + d]) return [-1, -1];
}
return [s1 + length - 1, s2 + length];
}class Solution {
public int[] threeEqualParts(int[] arr) {
int total = 0;
for (int v : arr) total += v;
if (total % 3 != 0) return new int[]{-1, -1};
if (total == 0) return new int[]{0, arr.length - 1};
int k = total / 3, n = arr.length;
int s1 = -1, s2 = -1, s3 = -1, c = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 1) {
if (c == 0) s1 = i;
if (c == k) s2 = i;
if (c == 2 * k) s3 = i;
c++;
}
}
int length = n - s3;
if (s1 + length > s2 || s2 + length > s3) return new int[]{-1, -1};
for (int d = 0; d < length; d++) {
if (arr[s1 + d] != arr[s2 + d] || arr[s2 + d] != arr[s3 + d])
return new int[]{-1, -1};
}
return new int[]{s1 + length - 1, s2 + length};
}
}vector<int> threeEqualParts(vector<int>& arr) {
int total = 0;
for (int v : arr) total += v;
if (total % 3 != 0) return {-1, -1};
if (total == 0) return {0, (int)arr.size() - 1};
int k = total / 3, n = arr.size();
int s1 = -1, s2 = -1, s3 = -1, c = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 1) {
if (c == 0) s1 = i;
if (c == k) s2 = i;
if (c == 2 * k) s3 = i;
c++;
}
}
int length = n - s3;
if (s1 + length > s2 || s2 + length > s3) return {-1, -1};
for (int d = 0; d < length; d++) {
if (arr[s1 + d] != arr[s2 + d] || arr[s2 + d] != arr[s3 + d])
return {-1, -1};
}
return {s1 + length - 1, s2 + length};
}Explanation
The three parts must represent the same binary number, which means they must each contain the same number of 1s. So the first thing we do is count the total ones; if it is not divisible by 3, a split is impossible.
If there are zero ones, every part is just zeros, so any split works and we return [0, n-1]. Otherwise each part needs exactly k = total / 3 ones. We record the index of the first one of each part: s1, s2 (the k-th one), and s3 (the 2k-th one).
The third part stretches from s3 to the end, so its meaningful length is n - s3 (this also fixes how many trailing digits each part must match). We line up all three parts at their first one and compare digit by digit for that length. If any of these blocks overlaps the next or any digit disagrees, we return [-1, -1].
This works because two binary numbers are equal exactly when, ignoring leading zeros, their digit patterns from the first 1 onward match. Leading zeros before s1, s2, s3 do not change the value.
Example: [1,0,1,0,1] has three ones, so k=1 and s1=0, s2=2, s3=4. The length is 1, the single digits all match, so the cut points are [0, 3] giving parts [1], [0,1], [0,1].