C++ में मोनोटोन बढ़ते अंक

मान लीजिए हमारे पास एक गैर-ऋणात्मक पूर्णांक N है, हमें N से कम या बराबर सबसे बड़ी संख्या ढूंढनी है जिसके अंक मोनोटोन रूप से बढ़ते हों। हम जानते हैं कि एक पूर्णांक के अंक मोनोटोन रूप से बढ़ते हैं यदि और केवल यदि आसन्न अंकों का प्रत्येक जोड़ा x और y, x ≤ y को संतुष्ट करता है। इसलिए यदि इनपुट 332 है, तो परिणाम 299 होगा।

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• s := N को स्ट्रिंग में बदलें, i := 1, n := s का आकार
• while i < n और s[i] >= s[i-1]:
  • i को 1 से बढ़ाएं
• if i < n:
  • while i > 0 और s[i-1] > s[i]:
    • i को 1 से घटाएं
    • s[i] को 1 से घटाएं
• j = i+1 से n-1 तक:
  • 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); 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.monotoneIncreasingDigits(332)); 
}

इनपुट

332

आउटपुट

299