Problem Statement
You are provided with an array arr consisting solely of the digits 0 and 1. The challenge is to split this array into three contiguous, non-empty parts such that each part represents the same binary value. The solution should provide indices [i, j] where i + 1 < j, categorizing the array into:
- The segment from
arr[0]toarr[i]as the first part, - The segment from
arr[i + 1]toarr[j - 1]as the second part, - The segment from
arr[j]toarr[arr.length - 1]as the third part.
The binary values of all three segments must be identical. If it's impossible to partition the array as described, the answer should be [-1, -1]. Each piece is considered in its entirety when determining its binary value, and leading zeros within segments are permissible.
Examples
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 * 104arr[i]is0or1
Approach and Intuition
Identify Total Ones: Start by counting the total number of
1s in the array. If this count isn't divisible by three, it's impossible to split the array into three parts with equal numbers of1s, hence return[-1, -1].Define Target Count: If the total count of
1s is divisible by three, define the target count for each segment astotal_ones / 3.Determine Segment Bounds: Use pointers or iterators to determine where each segment ends based on where the
1s are distributed:- The first part should end when the count of
1s reaches one third of the total. - The second part should end such that it also includes exactly one third of the total
1s. - The third part uses the remainder of the array.
- The first part should end when the count of
Leading Zeros Consideration: As leading zeros are allowed, zeros between counted
1s do not impact the binary value and must be handled appropriately within each segment.Verify Binary Equivalence: After determining potential split points, convert the binary representation of each section to its numeric value and verify whether all three values are indeed equal.
By following these steps, you can decide whether it is possible to split the array into three parts with equal binary values, and if it is, identify the exact indices that would allow such a division.
Solutions
- Java
- Python
class Solution {
private static final int[] NO_SOLUTION = new int[] {-1, -1};
public int[] divideIntoThreeParts(int[] array) {
int length = array.length;
// Calculate the total number of ones in the array.
int countOnes = 0;
for (int element : array) {
countOnes += element;
}
// If the total number of ones is not divisible by 3, return immediately.
if (countOnes % 3 != 0) {
return NO_SOLUTION;
}
// Establish the number of ones each part should have.
int onesPerPart = countOnes / 3;
if (onesPerPart == 0) {
return new int[] {0, length - 1};
}
// Variables to track the start and end of sequences of ones in three parts.
int start1 = -1, end1 = -1, start2 = -1, end2 = -1, start3 = -1, end3 = -1;
// Identify the bounds of ones for each of the three segments.
int onesCounter = 0;
for (int i = 0; i < length; ++i) {
if (array[i] == 1) {
onesCounter += 1;
if (onesCounter == 1) start1 = i;
if (onesCounter == onesPerPart) end1 = i;
if (onesCounter == onesPerPart + 1) start2 = i;
if (onesCounter == 2 * onesPerPart) end2 = i;
if (onesCounter == 2 * onesPerPart + 1) start3 = i;
if (onesCounter == 3 * onesPerPart) end3 = i;
}
}
// Extract parts to check if they're the same.
int[] segment1 = Arrays.copyOfRange(array, start1, end1 + 1);
int[] segment2 = Arrays.copyOfRange(array, start2, end2 + 1);
int[] segment3 = Arrays.copyOfRange(array, start3, end3 + 1);
if (!Arrays.equals(segment1, segment2) || !Arrays.equals(segment1, segment3)) {
return NO_SOLUTION;
}
// Calculate the minimum trailing zeros required after each part.
int zerosAfterFirst = start2 - end1 - 1;
int zerosAfterSecond = start3 - end2 - 1;
int trailingZeros = length - end3 - 1;
if (trailingZeros > Math.min(zerosAfterFirst, zerosAfterSecond)) {
return NO_SOLUTION;
}
return new int[] {end1 + trailingZeros, end2 + trailingZeros + 1};
}
}
The Java method divideIntoThreeParts within the Solution class aims to divide an input binary array into three contiguous parts, where each part contains an equal number of 1s and has the same binary value when converted from a binary array to a binary number. Here’s a breakdown of how the method accomplishes this:
- First, the method counts the total number of 1s in the array. If this count is not divisible by 3, the task is impossible, and the method returns
{-1, -1}to indicate no solution. - If there are zero 1s in the array, it means the array can be trivially divided into any three parts. In this case, it returns
{0, arr.length - 1}to signify the whole array as the solution. - Next, the code determines the positions of 1s which would mark the boundaries of the three equal parts. Using counters, it identifies the start and end indices for these parts.
- Arrays
segment1,segment2, andsegment3are created from the main array using the start and end indices previously found. If these derived arrays don’t match exactly in binary value, the method again signifies no solution by returning{-1, -1}. - Finally, the algorithm checks for the required number of trailing zeros after each part. If the actual number of zeros doesn’t satisfy the conditions, it returns
{-1, -1}. If all conditions are met, the indices just after the required zeros for the first two parts are returned, which give the exact split positions for the three parts.
This method ensures efficient validation of the array’s divisibility into three equal binary parts and smartly uses counting and array slicing to achieve the desired result.
class Solver:
def findSolution(self, array: List[int]) -> List[int]:
NO_RESULT = [-1, -1]
# Calculate total ones in the input array
sum_ones = sum(array)
if sum_ones % 3:
return NO_RESULT
# Find the necessary number of ones in each partition
ones_per_part = sum_ones // 3
if ones_per_part == 0:
return [0, len(array) - 1]
# Locate the starting and ending indices of the crucial 1s
ones_indices = []
count_ones = 0
for index, value in enumerate(array):
if value == 1:
count_ones += 1
if count_ones in {1, ones_per_part + 1, 2 * ones_per_part + 1}:
ones_indices.append(index)
if count_ones in {ones_per_part, 2 * ones_per_part, sum_ones}:
ones_indices.append(index)
# Indices for the 1s sections in the array
i1, j1, i2, j2, i3, j3 = ones_indices
# Check if the sequences of 1s are identical
if not(array[i1 : j1 + 1] == array[i2 : j2 + 1] == array[i3 : j3 + 1]):
return [-1, -1]
# Determine the gaps of zeros needed after each part
zeros_after_first = i2 - j1 - 1
zeros_after_second = i3 - j2 - 1
zeros_at_end = len(array) - j3 - 1
if zeros_at_end > min(zeros_after_first, zeros_after_second):
return NO_RESULT
j1 += zeros_at_end
j2 += zeros_at_end
return [j1, j2 + 1]
The given Python solution focuses on dividing an array of binary integers into three equal parts, such that the binary values represented by the three parts are identical. Here's a breakdown of how the solution proceeds:
Establish a result for scenarios where no valid partitioning is possible. This is indicated by returning
[-1, -1].Calculate the total count of
1s in the array. If this count isn't divisible by three, the immediate return is[-1, -1]since equitable partitioning is impossible.Determine the number of
1s that should ideally be in each of the three parts.If there are no
1s, meaning the array comprises entirely of0s, then the array can essentially be split anywhere, hence return[0, len(array) - 1].Traverse the array to detect pivotal indices which denote where the
1s critical for defining segments start and end.Using the gathered indices, check that the segments defined by these
1s actually contain identical sequences when compared to each other. If they do not match, again return[-1, -1].Determine the number of zeros following each identified segment to ensure there's enough space to align the parts correctly given that the final segment is allowed a certain slack with trailing zeros.
Adjust the end points (
j1andj2) of the first two parts to account for the available slack space of zeros at the end of the array, ensuring continuous sequences from each segment into the next.The indices
[j1, j2 + 1]are returned, suggesting valid split points if all conditions are satisfied, ensuring each segment is followed by an equivalent sequence of zeros to allow proper formatting as per the array's structure.
This process ensures that the array is divided fairly, with regards to the binary values depicted by each segment sharing an identical binary representation, validated through sequential and numeric alignments.
No comments yet.