Solution For Three Equal Parts

The Three Equal Parts problem on LeetCode is a problem that requires a bit of thinking, but with the right approach, it can be solved efficiently. Here is a detailed solution to the problem.

Problem Statement:

Given an array of binary integers, return three non-empty parts such that all of them have the same binary value.

Solution:

To solve the problem, we need to first identify if there exists a solution. In other words, we need to check if the array can be divided into three equal parts, each having the same binary value. To do this, we can perform the following steps:

Step 1: Calculate the total number of 1’s in the array.

Step 2: If the total number of 1’s is not divisible by three, return [-1,-1]. This is because there is no way we can divide the array into three parts having equal binary value.

Step 3: Calculate the value of onesInEachPart as the total number of 1’s divided by three.

Step 4: Traverse the array from right to left and count the number of 1’s in the last part of the array. Once you reach onesInEachPart, you have found the last part of the array. Store its index in a variable lastPartIndex.

Step 5: Traverse the array from right to left again and repeat Step 4 for the second part.

Step 6: Traverse the array from left to right starting from index 0 and count the number of 1’s in the first part of the array. Once you reach onesInEachPart, you have found the first part of the array. Store its index in a variable firstPartIndex.

Step 7: Traverse the array from left to right again and repeat Step 6 for the second part.

Step 8: Check if the three parts have equal binary value. If they do, return [firstPartIndex, lastPartIndex+1]. Otherwise, return [-1,-1].

Code:

Here is the code for the solution to the Three Equal Parts problem on LeetCode:

class Solution {
public:
vector<int> threeEqualParts(vector<int>& arr) {
vector<int> result{-1,-1};
int n=arr.size();
int ones=0;
for(int i=0; i<n; i++){
if(arr[i]==1) ones++;
}
if(ones % 3 != 0) return result;
if(ones == 0) return {0, n-1};
int onesInEachPart = ones / 3;
int lastPartIndex=-1, secondPartIndex=-1;
int cnt=0;
for(int i=n-1; i>=0; i--){
if(arr[i]==1) cnt++;
if(cnt==onesInEachPart){
lastPartIndex=i;
break;
}
}
cnt=0;
for(int i=lastPartIndex-1; i>=0; i--){
if(arr[i]==1) cnt++;
if(cnt==onesInEachPart){
secondPartIndex=i;
break;
}
}
cnt=0;
int firstPartIndex=0;
for(int i=0; i<n; i++){
if(arr[i]==1) cnt++;
if(cnt==onesInEachPart){
firstPartIndex=i;
break;
}
}
cnt=0;
int secondPartStart=secondPartIndex+1;
for(int i=secondPartStart; i<n; i++){
if(arr[i]==1) cnt++;
if(cnt==onesInEachPart){
int thirdPartStart=i+1;
for(int j=0; j<=onesInEachPart-1; j++){
if(arr[firstPartIndex+j]!=arr[secondPartIndex+j] || arr[secondPartIndex+j]!=arr[thirdPartStart+j]){
return result;
}
}
return {firstPartIndex+onesInEachPart-1, secondPartIndex+onesInEachPart};
}
}
return result;
}
};

The time complexity of this solution is O(n) as we are traversing the array only four times. The space complexity is O(1) as we are not using any extra memory other than the result vector.

Step by Step Implementation For Three Equal Parts

/**
 * Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

A[0], A[1], ..., A[i] is the first part,
A[i+1], A[i+2], ..., A[j-1] is the second part,
A[j], A[j+1], ..., A[A.length - 1] is the third part.
All three parts have equal binary value.
If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents.  For example, [1,1,0] represents 6 in decimal, not 3.  Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

 

Example 1:

Input: [1,0,1,0,1]
Output: [0,3]
Example 2:

Input: [1,1,0,1,1]
Output: [-1,-1]
 

Note:

3 <= A.length <= 30000
A[i] == 0 or A[i] == 1
 */

class Solution {
    public int[] threeEqualParts(int[] A) {
        int sum = 0; 
        for (int i = 0; i < A.length; i++) {
            sum += A[i]; 
        }
        
        if (sum % 3 != 0) {
            return new int[] {-1, -1};
        }
        
        int parts = sum / 3; 
        int i1 = 0, i2 = 0, i3 = 0;
        int j1 = 0, j2 = 0, j3 = A.length - 1;
        
        while (i3 < A.length && A[i3] == 0) {
            i3++;
        }
        
        while (j3 >= 0 && A[j3] == 0) {
            j3--;
        }
        
        if (i3 > j3) {
            return new int[] {0, A.length - 1};
        }
        
        int count = 0;
        
        while (count < parts) {
            count += A[i3];
            i3++;
        }
        
        i2 = i3 - 1;
        count = 0;
        
        while (count < parts) {
            count += A[j3];
            j3--;
        }
        
        j2 = j3 + 1;
        
        while (i1 < A.length && A[i1] == 0) {
            i1++;
        }
        
        if (i1 == A.length) {
            return new int[] {0, A.length - 1};
        }
        
        while (j1 >= 0 && A[j1] == 0) {
            j1--;
        }
        
        if (j1 < 0) {
            return new int[] {-1, -1};
        }
        
        while (i1 <= i2 && i2 <= j2 && j2 <= j1) {
            if (A[i1] == A[i2] && A[i2] == A[j2]) {
                i1++;
                i2++;
                j2++;
            } else {
                return new int[] {-1, -1};
            }
        }
        
        return new int[] {i1 - 1, j2};
    }
}

Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

A[0], A[1], ..., A[i] is the first part,
A[i+1], A[i+2], ..., A[j-1] is the second part,
and A[j], A[j+1], ..., A[A.length - 1] is the third part.
All three parts have equal binary value.
If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents.  For example, [1,1,0] represents 6 in decimal, not 3.  Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

def threeEqualParts(self, A):
        #find the number of 1's in the array
        count = 0
        for i in range(len(A)):
            if A[i] == 1:
                count += 1
                
        #if the number of 1's is not divisible by 3, then it is not possible to have 3 equal parts
        if count % 3 != 0:
            return [-1, -1]
        
        #find the number of 1's in each part
        part = count // 3
        
        #find the index of the last 1 in the first part, the index of the first 1 in the second part, and the index of the last 1 in the second part
        i, j, k = 0, 0, 0
        count = 0
        while count <= part:
            if A[i] == 1:
                count += 1
            i += 1
        while count <= 2*part:
            if A[j] == 1:
                count += 1
            j += 1
        while count <= 3*part:
            if A[k] == 1:
                count += 1
            k += 1
            
        #compare the first part with the second part and the second part with the third part
        while i < j and j < k:
            if A[i] != A[j] or A[j] != A[k]:
                return [-1, -1]
            i += 1
            j += 1
            k += 1
            
        return [i-1, j]

/**
 * @param {number[]} A
 * @return {number[]}
 */
var threeEqualParts = function(A) {
    
};

Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

A[0], A[1], ..., A[i] is the first part,
A[i+1], A[i+2], ..., A[j-1] is the second part,
A[j], A[j+1], ..., A[A.length - 1] is the third part.
Each part can have any length.
Return null if the array cannot be divided into three parts.

Note:

A will have length between 1 and 500.
A[i] will be 0 or 1.

Solution:

We can use a greedy approach to solve this problem. First, we will compute the sum of all the elements in the array. This will tell us the total number of 1s in the array.

If the sum is not divisible by 3, then we know it is not possible to divide the array into 3 parts with equal sums.

Otherwise, we can keep track of the current sum of each part. Once we reach a sum that is equal to the sum / 3, we know we have found one part. We can then reset the current sum and continue looking for the next part.

If we find the third part and the current sum is also equal to sum / 3, then we know we have found a valid solution and can return the indices of the left and right boundaries of the three parts.

If we reach the end of the array without finding a valid solution, then we know it is not possible to divide the array into 3 parts with equal sums and we can return null.

public class Solution {
    public int[] ThreeEqualParts(int[] A) {
        
        //find the sum of all the elements in the array
        int sum = 0;
        for(int i = 0; i < A.Length; i++){
            sum += A[i];
        }
        
        //if the sum is not divisible by 3, then we cannot split the array into 3 equal parts
        if(sum % 3 != 0){
            return new int[] {-1, -1};
        }
        
        //find the sum of each part
        int partSum = sum / 3;
        
        //initialize the three parts of the array
        int[] part1 = new int[A.Length];
        int[] part2 = new int[A.Length];
        int[] part3 = new int[A.Length];
        
        //initialize the index for each part
        int part1Index = 0;
        int part2Index = 0;
        int part3Index = 0;
        
        //go through the original array and add each element to the appropriate part
        for(int i = 0; i < A.Length; i++){
            if(part1Index < part1.Length){
                part1[part1Index] = A[i];
                part1Index++;
            }
            else if(part2Index < part2.Length){
                part2[part2Index] = A[i];
                part2Index++;
            }
            else{
                part3[part3Index] = A[i];
                part3Index++;
            }
        }
        
        //check if the three parts are equal
        if(part1.SequenceEqual(part2) && part2.SequenceEqual(part3)){
            return new int[] {part1Index - 1, part2Index};
        }
        else{
            return new int[] {-1, -1};
        }
    }
}