927. Three Equal Parts

leetcode hard

#array#csharp#hard#leetcode

Task

Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с i + 1 < j, такой что: arr[0], arr[1], ..., arr[i] - это первая часть, arr[i + 1], arr[i + 2], ...., arr[j - 1] - вторая часть, и arr[j], arr[j + 1], ..., arr[arr.length - 1] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение.

Пример:

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

Output: [0,3]

C# solution

matched/original

public class Solution {
    public int[] ThreeEqualParts(int[] arr) {
        int ones = 0;
        foreach (int num in arr) {
            ones += num;
        }
        if (ones % 3 != 0) return new int[]{-1, -1};
        if (ones == 0) return new int[]{0, arr.Length - 1};
        int partOnes = ones / 3;
        int first = 0, second = 0, third = 0, cnt = 0;
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == 1) {
                if (cnt == 0) first = i;
                else if (cnt == partOnes) second = i;
                else if (cnt == 2 * partOnes) third = i;
                cnt++;
            }
        }
        while (third < arr.Length && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++;
            second++;
            third++;
        }
        if (third == arr.Length) return new int[]{first - 1, second};
        return new int[]{-1, -1};
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& ThreeEqualParts(vector<int>& arr) {
        int ones = 0;
        foreach (int num in arr) {
            ones += num;
        }
        if (ones % 3 != 0) return new int[]{-1, -1};
        if (ones == 0) return new int[]{0, arr.size() - 1};
        int partOnes = ones / 3;
        int first = 0, second = 0, third = 0, cnt = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] == 1) {
                if (cnt == 0) first = i;
                else if (cnt == partOnes) second = i;
                else if (cnt == 2 * partOnes) third = i;
                cnt++;
            }
        }
        while (third < arr.size() && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++;
            second++;
            third++;
        }
        if (third == arr.size()) return new int[]{first - 1, second};
        return new int[]{-1, -1};
    }
}

Java solution

matched/original

class Solution {
    public int[] threeEqualParts(int[] arr) {
        int ones = 0;
        for (int num : arr) {
            ones += num;
        }
        if (ones % 3 != 0) return new int[]{-1, -1};
        if (ones == 0) return new int[]{0, arr.length - 1};

        int partOnes = ones / 3;
        int first = 0, second = 0, third = 0, cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                if (cnt == 0) first = i;
                else if (cnt == partOnes) second = i;
                else if (cnt == 2 * partOnes) third = i;
                cnt++;
            }
        }

        while (third < arr.length && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++;
            second++;
            third++;
        }

        if (third == arr.length) return new int[]{first - 1, second};
        return new int[]{-1, -1};
    }
}

JavaScript solution

matched/original

var threeEqualParts = function(arr) {
    const ones = arr.reduce((acc, val) => acc + val, 0);
    if (ones % 3 !== 0) return [-1, -1];
    if (ones === 0) return [0, arr.length - 1];

    const partOnes = ones / 3;
    let first = 0, second = 0, third = 0, cnt = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 1) {
            if (cnt === 0) first = i;
            else if (cnt === partOnes) second = i;
            else if (cnt === 2 * partOnes) third = i;
            cnt++;
        }
    }

    while (third < arr.length && arr[first] === arr[second] && arr[first] === arr[third]) {
        first++;
        second++;
        third++;
    }

    if (third === arr.length) return [first - 1, second];
    return [-1, -1];
};

Python solution

matched/original

def threeEqualParts(arr):
    ones = sum(arr)
    if ones % 3 != 0:
        return [-1, -1]
    if ones == 0:
        return [0, len(arr) - 1]
    
    part_ones = ones // 3
    first = second = third = cnt = 0
    for i, val in enumerate(arr):
        if val == 1:
            if cnt == 0:
                first = i
            elif cnt == part_ones:
                second = i
            elif cnt == 2 * part_ones:
                third = i
            cnt += 1
    
    while third < len(arr) and arr[first] == arr[second] == arr[third]:
        first += 1
        second += 1
        third += 1
    
    if third == len(arr):
        return [first - 1, second]
    return [-1, -1]

Explanation

Algorithm

Подсчитать количество единиц в массиве.

Если количество единиц не делится на три, вернуть [-1, -1].

Найти индексы начала каждой части, игнорируя ведущие нули.

Использовать эти индексы для проверки, могут ли три части быть одинаковыми.

Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1].

😎