समस्याओं की संख्या गिनने के लिए C++ प्रोग्राम को सूची के बाएँ या दाएँ छोर से हल किया जा सकता है

मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी A है और एक अन्य संख्या k है। विचार करें कि किसी प्रतियोगिता में n समस्याएं हैं। अमल का समस्या समाधान कौशल k है। अमल हमेशा सूची के किसी भी छोर से समस्या हल करता है। और वह उस समस्या का समाधान नहीं कर सकता जिसकी कठिनाई k से अधिक है। जब बाएँ और दाएँ समस्याओं की कठिनाई k से अधिक होती है, तो वह रुक जाता है। हमें गिनना होगा कि वह कितनी समस्याओं का समाधान कर सकता है। A[i] ith समस्या की कठिनाई का प्रतिनिधित्व करता है।

इसलिए, यदि इनपुट ए =[4, 2, 3, 1, 5, 1, 6, 4] जैसा है; k =4, तो आउटपुट 5 होगा, क्योंकि शुरू में सबसे बाईं ओर की समस्या को 4 के साथ हल करें, फिर सबसे दाईं ओर की समस्या को 4 से हल करें, फिर दाईं ओर की सबसे अधिक समस्या को हल नहीं कर सकते, फिर बाएं से, कठिनाई 2, 3 और 1 के साथ समस्याओं को हल करें। कुल 5 समस्याओं का समाधान किया जा सकता है।

कदम

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

n := size of A
l := 0
r := n - 1
for initialize i := 0, when i < n, update (increase i by 1), do:
   if A[i] <= k and l is same as i, then:
      (increase l by 1)
while A[r] <= k, do:
   (decrease r by 1)
if l is same as n, then:
   return n
Otherwise
   return n - 1 - r + l

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, int k) {
   int n = A.size();
   int l = 0, r = n - 1;
   for (int i = 0; i < n; ++i) {
      if (A[i] <= k && l == i)
         ++l;
   }
   while (A[r] <= k)
      --r;
   if (l == n)
      return n;
   else
      return n - 1 - r + l;
}
int main() {
   vector<int> A = { 4, 2, 3, 1, 5, 1, 6, 4 };
   int k = 4;
   cout << solve(A, k) << endl;
}

इनपुट

{ 4, 2, 3, 1, 5, 1, 6, 4 }, 4

आउटपुट

5