একটি ০ এবং ১ দিয়ে গঠিত অ্যারে A দেওয়া আছে, আমাদের কতগুলো নন-এম্পটি সাবঅ্যারের যোগফল S তা খুঁজে বের করতে হবে। ইনপুট [1,0,1,0,1], S = 2 হলে ফলাফল ৪। সাবঅ্যারগুলো হল [1,0,1,0,1], [1,0,1,0,1], [1,0,1,0,1], [1,0,1,0,1]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
atMost() নামে একটি মেথড সংজ্ঞায়িত করুন, যা অ্যারে A এবং পূর্ণসংখ্যা x নেবে
যদি x < 0 হয়, ০ রিটার্ন করুন, j := 0, ret := 0 সেট করুন
i = 0 থেকে A.size()-1 পর্যন্ত লুপ চালান
x := x - A[i]
যখন x < 0
x := x + A[j], j++
ret := ret + i - j + 1
ret রিটার্ন করুন
মেইন মেথড থেকে - ret := atMost(A, S) - atMost(A, S-1)
ret রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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
