सी ++ में योग के साथ बाइनरी सबएरे

मान लीजिए कि 0s और 1s की एक सरणी A दी गई है, हमें यह पता लगाना है कि कितने गैर-रिक्त उपसरणियों का योग S है? तो अगर इनपुट [1,0,1,0,1] और एस =2 जैसा है, तो परिणाम 4 होगा, क्योंकि उप-सरणी [1,0,1,0,1], [1,0 ,1,0,1], [1,0,1,0,1], [1,0,1,0,1]।

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

• एटमोस्ट () नामक एक विधि को परिभाषित करें, यह सरणी ए और पूर्णांक x लेगा

• यदि x <0 है, तो 0 लौटाएं, j :=0 सेट करें और रिट सेट करें:=0

• मैं के लिए 0 से ए के आकार के बीच

  • x को A[i]

    . से घटाएं

  • जबकि x <0

    • x को A[j] से बढ़ाएँ, j को 1 से बढ़ाएँ

  • रिट:=रिट + आई - जे + 1

• वापसी रिट

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

• ret :=atMost(A, S) – atMost(A, S – 1)

• वापसी रिट

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int atMost(vector <int>& A, int x){
      if(x < 0) return 0;
      int j = 0;
      int ret = 0;
      for(int i = 0; i < A.size(); i++){
         x -= A[i];
         while(x < 0){
            x += A[j];
            j++;
         }
         ret += i - j + 1;
      }
      return ret;
   }
   int numSubarraysWithSum(vector<int>& A, int S) {
      return atMost(A, S) - atMost(A, S - 1);
   }
};
main(){
   vector<int> v1 = {1,0,1,0,1};
   Solution ob;
   cout << (ob.numSubarraysWithSum(v1, 2));
}

इनपुट

[1,0,1,0,1]

आउटपुट

4