Problem
Given an arrayĀ A
Ā ofĀ 0
s andĀ 1
s, 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, andA[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
Solution:
each part should have the same number of 1 s.
Find the suffix (without leading os) of the last part which should have 1/3 of the total ones.
Time complexity: O(n^2) in theory but close to O(n) in practice
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, 44 ms class Solution { public: vector<int> threeEqualParts(vector<int>& A) { string s(begin(A), end(A)); int ones = accumulate(begin(A), end(A), 0); if (ones % 3 != 0) return {-1, -1}; if (ones == 0) return {0, A.size() - 1}; ones /= 3; int right = A.size() - 1; while (ones) if (A[right--]) --ones; string suffix(begin(s) + right + 1, end(s)); size_t l = suffix.length(); size_t left = s.find(suffix); if (left == std::string::npos) return {-1, -1}; size_t mid = s.find(suffix, left + l); if (mid == std::string::npos || mid + 2 * l > s.length()) return {-1, -1}; return {left + l - 1, mid + l}; } }; |