Sponsored
Sponsored
In this approach, we iterate through the array while counting the number of 1s. We need to ensure that the number of 1s is divisible by 3, otherwise it's impossible to split the array with equal parts. If it's divisible, each part must contain the same number of 1s.
After determining the number of 1s each part should have, we traverse the array again to find possible split points, and validate if the parts have equal binary values by comparing.
Time Complexity: O(n), where n is the length of the array, as we are traversing the array a few times.
Space Complexity: O(1), as no additional space is used except for variables.
1function threeEqualParts(arr) {
2 const numOfOnes = arr.reduce((acc, num) => acc + num);
3 if (numOfOnes % 3 !== 0) return [-1, -1];
4 if (numOfOnes === 0) return [0, arr.length - 1];
5
6 let target = numOfOnes / 3;
7 let first = -1, second = -1, third = -1, oneCount = 0;
8
9 for (let i = 0; i < arr.length; i++) {
10 if (arr[i] === 1) {
11 if (oneCount === 0) first = i;
12 if (oneCount === target) second = i;
13 if (oneCount === 2 * target) third = i;
14 oneCount++;
15 }
16 }
17
18 const length = arr.length - third;
19 if (check(arr, first, second, third, length)) {
20 return [first + length - 1, second + length];
21 }
22 return [-1, -1];
23}
24
25function check(arr, first, second, third, length) {
26 for (let i = 0; i < length; i++) {
27 if (arr[first + i] !== arr[second + i] || arr[second + i] !== arr[third + i]) return false;
28 }
29 return true;
30}This JavaScript solution works similarly to the Python one. It first calculates the number of 1s and checks if they can be divided into three equal parts. It then determines the starting indices of the three parts that should each contain an equal number of 1s.
The `check` function validates if the segments starting at these indices are equal. If equal, it returns the split indices.
This approach uses hashing to store the indices of 1s as keys and their count as values for faster retrieval and comparison.
Once we determine the number of 1s each part should have (after verifying it's divisible by 3), we use these indices to segment the array into candidate parts. Hashing ensures we efficiently compare these binary segments.
Time Complexity: O(n)
Space Complexity: O(1)
1public int[] ThreeEqualParts(int[] arr)
2{
3 int numOfOnes = arr.Count(x => x == 1);
4 if (numOfOnes % 3 != 0) return new int[] { -1, -1 };
5 if (numOfOnes == 0) return new int[] { 0, arr.Length - 1 };
6
7 int target = numOfOnes / 3;
8 int first = -1, second = -1, third = -1, count = 0;
for (int i = 0; i < arr.Length; ++i)
{
if (arr[i] == 1)
{
if (count == 0) first = i;
if (count == target) second = i;
if (count == 2 * target) third = i;
count++;
}
}
int partLen = arr.Length - third;
if (ArePartsEqual(arr, first, second, third, partLen))
{
return new int[] { first + partLen - 1, second + partLen };
}
return new int[] { -1, -1 };
}
private bool ArePartsEqual(int[] arr, int first, int second, int third, int partLen)
{
for (int i = 0; i < partLen; ++i)
{
if (arr[first + i] != arr[second + i] || arr[second + i] != arr[third + i])
{
return false;
}
}
return true;
}This C# solution is similar in logic to the other languages, ensuring the array can be divided into three equal parts of ones. We store the locations of the ones using index positions, and only move once processed sections are validated as the same.