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.
1def three_equal_parts(arr):
2 num_of_ones = arr.count(1)
3 if num_of_ones % 3 != 0:
4 return [-1, -1]
5 if num_of_ones == 0:
6 return [0, len(arr) - 1]
7 target = num_of_ones // 3
8 first = second = third = one_count = 0
9 for i, bit in enumerate(arr):
10 if bit == 1:
11 if one_count == 0:
12 first = i
13 elif one_count == target:
14 second = i
15 elif one_count == 2 * target:
16 third = i
17 one_count += 1
18 length = len(arr) - third
19 if arr[first:first+length] == arr[second:second+length] == arr[third:]:
20 return [first + length - 1, second + length]
21 return [-1, -1]This Python solution first counts the number of 1s in the array. If the count is not divisible by 3, it returns [-1, -1] as it's impossible to divide the array into three parts with equal binary values. If the array contains no 1s, it returns [0, length-1] since every part can be all 0s. It then finds the starting indices of the three parts, where each part should contain an equal number of 1s.
It checks if the segments starting at these indices are of the same value. If yes, it returns the indices just before the start of the second and third parts.
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.