Three Equal Parts - Practice Coding Problems

Three Equal Parts - Problem

Array Math Hard

You are given an array arr which consists of only zeros and ones. Divide the array into three 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:

arr[0], arr[1], ..., arr[i] is the first part
arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part
arr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part

All three parts have equal binary values. If it is not possible, return [-1, -1].

Note: 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.

Input & Output

Example 1 — Valid Split

$ Input: arr = [0,1,0,1,0,1]

› Output: [0,3]

💡 Note: Split into [0], [1,0], [1,0,1]. Values: 0, 2, 5 - not equal. Actually: [0,1], [0,1], [0,1] → all equal to 1.

Example 2 — All Zeros

$ Input: arr = [0,0,0,0,0,0]

› Output: [0,2]

💡 Note: All parts will be 0 regardless of split position, so any valid split like [0], [0], [0,0,0,0] works.

Example 3 — Impossible Split

$ Input: arr = [1,1,0,1,1]

› Output: [-1,-1]

💡 Note: Total ones = 4, not divisible by 3, so impossible to create three equal binary values.

Constraints

3 ≤ arr.length ≤ 3 × 10⁴
arr[i] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Array

Binary array [0,1,0,1,0,1] with 3 ones total

Find Pattern

Each part needs 1 one. Pattern is '01' (binary value 1)

Valid Split

Split at positions [1,4]: [0,1], [0,1], [0,1] - all equal

Key Takeaway

🎯 Key Insight: Count total 1s first - if not divisible by 3, return [-1,-1] immediately

Asked in

f Facebook 35 G Google 28 a Amazon 22

The key insight is that if the total number of 1s isn't divisible by 3, it's impossible to create three equal parts. The optimal approach uses pattern matching - find the binary pattern of the first third of 1s, then verify this exact pattern appears three times consecutively. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Split Points	O(n³)	O(n)	Try all possible ways to split the array into three parts and check if they're equal
Pattern Matching Approach	O(n)	O(1)	Count total ones, find the target pattern, then locate it three times in the array

Brute Force - Try All Split Points — Algorithm Steps

Try all valid split positions i and j where i + 1 < j
Extract three parts: [0..i], [i+1..j-1], [j..n-1]
Convert each part to binary string and compare for equality

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Split i=2, j=4

Split [0,1,0,1,1,0] into parts [0,1], [0], [1,1,0]

Convert to Decimal

Part1: 01→1, Part2: 0→0, Part3: 110→6

Compare Values

1≠0≠6, so try next split position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* arr, int arrSize, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    // Try all possible split points
    for (int i = 0; i < arrSize - 2; i++) {
        for (int j = i + 2; j < arrSize; j++) {
            // Convert parts to integers
            int val1 = 0, val2 = 0, val3 = 0;
            
            // Calculate val1 (0 to i)
            for (int k = 0; k <= i; k++) {
                val1 = val1 * 2 + arr[k];
            }
            
            // Calculate val2 (i+1 to j-1)
            for (int k = i + 1; k < j; k++) {
                val2 = val2 * 2 + arr[k];
            }
            
            // Calculate val3 (j to arrSize-1)
            for (int k = j; k < arrSize; k++) {
                val3 = val3 * 2 + arr[k];
            }
            
            if (val1 == val2 && val2 == val3) {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    
    result[0] = -1;
    result[1] = -1;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (*token >= '0' && *token <= '9') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(arr, size, &returnSize);
    
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops for split positions O(n²) and string comparison O(n) for each combination

⚠ Quadratic Growth

Space Complexity

O(n)

String creation for binary representation of each part

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Split Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler