C++-এ একঘাত বৃদ্ধিমান অঙ্ক

ধরুন আমাদের একটি অঋণাত্মক পূর্ণসংখ্যা N আছে, আমাদের N-এর চেয়ে বড় বা সম এমন সর্বোচ্চ সংখ্যা খুঁজে বের করতে হবে যার অঙ্কগুলি একঘাতভাবে বৃদ্ধিমান। আমরা জানি একটি পূর্ণসংখ্যার একঘাত বৃদ্ধিমান অঙ্ক থাকলে তার প্রতিটি অনুরূপ অঙ্ক জোড়া x এবং y সन्नিবেশ x <= y কে সিদ্ধ করে। তাই যদি ইনপুট 332 হয়, তবে ফলাফল হবে 299।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −

• s := N স্ট্রিং হিসেবে, i := ১, n := s-এর আকার
• যখন i < n এবং s[i] >= s[i – ১]
  • i ১ বৃদ্ধি করুন
• যদি i < n
  • যখন i > ০ এবং s[i – ১] > s[i], তবে
    • i ১ হ্রাস করুন
    • s[i] ১ হ্রাস করুন
• j = i + 1 থেকে n পর্যন্ত
  • s[j] := ‘9’
• s কে সংখ্যা হিসেবে ফেরত দিন

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −

উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution { public:    int monotoneIncreasingDigits(int N) {       string s = to_string(N);       int i = 1;       int n = s.size();       while(i < n && s[i] >= s[i - 1]) i++;       if( i < n)       while(i > 0 && s[i - 1] > s[i]){          i--;          s[i]--;       }       for(int j = i + 1; j < n; j++)s[j] = '9';       return stoi(s);    } }; main(){    Solution ob;    cout << (ob.monotoneIncreasingDigits(332)); }

ইনপুট

332

আউটপুট

299