C++ में तीन समान भाग

मान लीजिए कि हमारे पास 0s और 1s की एक सरणी A है, हमें सरणी को 3 गैर-रिक्त भागों में विभाजित करना होगा जैसे कि ये सभी भाग समान बाइनरी मान का प्रतिनिधित्व करते हैं। यदि यह संभव है, तो किसी भी [i, j] को i+1

• 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]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें getIdx(), यह एक सरणी लेगा a, बाएँ, दाएँ,

• जबकि (बाएं <दाएं और एक [बाएं] 0 के समान है), करें -

  • (बाएं 1 से बढ़ाएं)

• जबकि दाएं <(int)a.size(), करते हैं -

  • अगर एक [बाएं] एक [दाएं] के बराबर नहीं है, तो, वापसी -1

  • (बाएं से 1 बढ़ाएं), (1 से दाएं बढ़ाएं)

• बाएं लौटें - 1

• मुख्य विधि से निम्न कार्य करें -

• आकार 2 के एक सरणी को परिभाषित करें इसे -1 से भरें

• संख्या:=0, n:=A का आकार

• इनिशियलाइज़ i:=0 के लिए, जब i

  • num :=num + 1 जब (A[i] 1 के समान हो, अन्यथा 0

• अगर num mod 3 0 के बराबर नहीं है, तो -

  • वापसी रिट

• यदि संख्या 0 के समान है, तो -

  • वापसी { 0, 2 }

• अनुरोध :=संख्या / 3

• आईडीएक्स :=n - 1

• प्रारंभिक अस्थायी के लिए:=0, जब idx> =0 और अस्थायी

  • अस्थायी:=अस्थायी + 1 जब (ए [आईडीएक्स] 1 के समान है), अन्यथा 0

• (आईडीएक्स को 1 से बढ़ाएं)

• फर्स्टएंड :=getIdx(A, 0, idx)

• अगर पहलेअंत <0, तो -

  • वापसी रिट

• सेकेंडएंड :=getIdx(A, firstEnd + 1, idx)

• अगर सेकेंडएंड <0, तो -

  • वापसी रिट

• वापसी {फर्स्टएंड, सेकेंडएंड + 1}

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,1,0,1,1};
   print_vector(ob.threeEqualParts(v));
}

इनपुट

{0,1,0,1,1}

आउटपुट

[1, 4, ]