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.
1public int[] threeEqualParts(int[] arr) {
2 int numOfOnes = 0;
3 for (int num : arr) numOfOnes += num;
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, oneCount = 0;
9 for (int 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 int length = arr.length - third;
19 if (isValid(arr, first, second, third, length)) {
20 return new int[]{first + length - 1, second + length};
21 }
22 return new int[]{-1, -1};
23}
24
25private boolean isValid(int[] arr, int first, int second, int third, int length) {
26 for (int 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 Java solution calculates the number of 1s and ensures they can be divided into three equal parts. Then it finds the starting indices for the segments to contain equal 1s. A helper method checks if the segments starting at these indices yield the same binary value.
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.