সমস্যা বিবরণ
বাইনারি অ্যারে A দেওয়া থাকলে, সেটিকে ৩টি নন-ইম্পটি অংশে ভাগ করতে হবে যাতে তিনों পার্টের বাইনারি মান সমান হয়। সম্ভব হলে [i, j] রিটার্ন করুন (i+1 < j), নাহলে [-1, -1]।
উদাহরণ
A = [0,1,0,1,1] → আউটপুট = [0, 4]
সমাধান পদ্ধতি
- টোটাল ১-এর সংখ্যা ৩ দিয়ে বিভাজ্য হলেই সম্ভব।
- শেষ পার্টের ১-গুলোর পজিশন থেকে ট্রেলিং জিরো নির্ণয় করা হয়।
- getIdx() ফাংশন দিয়ে লিডিং জিরো স্কিপ করে পার্ট বাউন্ডারি বের করা হয়।
- প্রথম ও দ্বিতীয় পার্টের বাউন্ডারি মিলিয়ে যাচাই করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
cout << "]" << endl;
}
class Solution {
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;
}
public:
vector<int> threeEqualParts(vector<int>& A) {
vector<int> ret(2, -1);
int num = 0, n = A.size();
for (int x : A) num += (x == 1);
if (num % 3 != 0) return ret;
if (num == 0) return {0, 2};
int req = num / 3, 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 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]
