मान लीजिए हमारे पास 0 और 1 की एक सरणी A है, हमें सरणी को 3 गैर-खाली भागों में विभाजित करना है जैसे कि ये सभी भाग समान बाइनरी मान दर्शाते हैं। यदि संभव है, तो कोई भी [i, j] लौटाएं जहां i+1 < j, जैसे कि:
A[0], A[1], ..., A[i] पहला भाग है;
A[i+1], A[i+2], ..., A[j-1] दूसरा भाग है, और
A[j], A[j+1], ..., A[A.length-1] तीसरा भाग है।
सभी तीन भागों का बाइनरी मान समान है। यदि संभव नहीं है, तो [-1, -1] वापस करें।
उदाहरण के लिए, यदि इनपुट [0,1,0,1,1] है, तो आउटपुट [0,4] होगा।
हल करने का दृष्टिकोण
कुल 1s गिनें; यदि 3 से विभाज्य नहीं है, तो [-1, -1] वापस करें
यदि कोई 1 नहीं है, तो [0, 2] वापस करें
प्रत्येक भाग में req = कुल_1s/3 1s होने चाहिए
अंत से तीसरे भाग की शुरुआत ढूंढें (अंतिम req 1s)
getIdx का उपयोग करके अग्रणी शून्यों को छोड़कर पहले और दूसरे भाग की सीमाएं ढूंढें
सत्यापित करें कि सभी तीन भागों में समान बिट्स हैं
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> threeEqualParts(vector<int>& A){
vector<int> ret(2, -1);
int num = 0;
int n = A.size();
for (int i = 0; i < n; i++) num += (A[i] == 1);
if (num % 3 != 0) return ret;
if (num == 0) return { 0, 2 };
int req = num / 3;
int idx = n - 1;
for (int temp = 0; idx >= 0 && temp < req; idx--) {
temp += A[idx] == 1;
}
idx++;
int firstEnd = getIdx(A, 0, idx);
if (firstEnd < 0) return ret;
int secondEnd = getIdx(A, firstEnd + 1, idx);
if (secondEnd < 0) return ret;
return { firstEnd, secondEnd + 1 };
}
int getIdx(vector<int>& a, int left, int right){
while (left < right && a[left] == 0) left++;
while (right < (int)a.size()) {
if (a[left] != a[right]) return -1;
left++; right++;
}
return left - 1;
}
};
int main(){
Solution ob;
vector<int> v = {0,1,0,1,1};
print_vector(ob.threeEqualParts(v));
return 0;
}
इनपुट
{0,1,0,1,1}
आउटपुट
[1, 4, ]