Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में N को 25 से विभाज्य बनाने के लिए दिए गए मूव्स की न्यूनतम संख्या

समस्या कथन

अग्रणी शून्य के बिना एक संख्या N दी गई है। N को 25 से विभाज्य बनाने के लिए आवश्यक न्यूनतम मूव्स की संख्या ढूंढें। प्रत्येक मूव में, कोई भी दो आसन्न अंकों को स्वैप कर सकता है और यह सुनिश्चित करना होगा कि किसी भी समय संख्या में कोई अग्रणी शून्य न हो। यदि N को 25 से विभाज्य बनाना संभव नहीं है तो -1 प्रिंट करें।

यदि N=5071, तो 25 से विभाज्य बनाने के लिए 4 मूव्स आवश्यक हैं:

5071 → 5701 → 7501 → 7510 → 7150

एल्गोरिदम

1. संख्या में अंकों के सभी जोड़ों पर पुनरावृति करें। मान लें जोड़ी में पहला अंक स्थिति 'i' पर है और दूसरा स्थिति 'j' पर।
2. इन अंकों को संख्या में अंतिम दो स्थितियों पर रखें
3. यदि संख्या में अग्रणी शून्य है। बाएं सबसे दूर के गैर-शून्य अंक को ढूंढें और इसे पहली स्थिति पर ले जाएं।
4. यदि वर्तमान संख्या 25 से विभाज्य है तो स्वैप की संख्या के साथ उत्तर अपडेट करें

C++ उदाहरण

#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;

int requiredMoves(long long n) {
    string str = to_string(n);
    int ans = INT_MAX;
    int len = str.size();
    
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            if (i == j) continue;
            string temp = str;
            int cnt = 0;
            for (int k = i; k < len - 1; ++k) {
                swap(temp[k], temp[k + 1]); ++cnt;
            }
            for (int k = j - (j > i); k < len - 2; ++k) {
                swap(temp[k], temp[k + 1]); ++cnt;
            }
            int pos = -1;
            for (int k = 0; k < len; ++k) {
                if (temp[k] != '0') { pos = k; break; }
            }
            for (int k = pos; k > 0; --k) {
                swap(temp[k], temp[k - 1]); ++cnt;
            }
            long long num = atoll(temp.c_str());
            if (num % 25 == 0) ans = min(ans, cnt);
        }
    }
    if (ans == INT_MAX) return -1;
    return ans;
}

int main() {
    int n = 5071;
    cout << "Minimum required moves: " << requiredMoves(n) << endl;
    return 0;
}

आउटपुट

Minimum required moves: 4
  1. - C++ में माध्यिका को x के बराबर बनाने के लिए जोड़े जाने वाले न्यूनतम तत्व

    समस्या कथन आकार n की एक सरणी arr और तत्व x दिया गया है, सरणी में जोड़े जाने वाले न्यूनतम तत्वों की संख्या ढूंढें ताकि माध्यिका (median) x के बराबर हो जाए। लंबाई n की सरणी में माध्यिका वह तत्व है जो तत्वों को गैर-घटते क्रम में सॉर्ट करने के बाद स्थिति (n-1)/2 पर आता है। उदाहरण के लिए, नीचे दी गई सरणी

  1. - C++ में सरणी को अच्छा बनाने के लिए हटाए जाने वाले न्यूनतम तत्व

    समस्या कथन एक सरणी arr दी गई है, सरणी को अच्छा बनाने के लिए हटाए जाने वाले न्यूनतम तत्वों की संख्या ढूंढें। एक अनुक्रम a1, a2, a3...an को अच्छा कहा जाता है यदि प्रत्येक तत्व a[i] के लिए, एक तत्व a[j] (i ≠ j) मौजूद होता है जैसे कि a[i] + a[j] 2 की घात हो। arr1[] = {1, 1, 7, 1, 5} उपरोक्त सरणी में यदि

  1. - C++ में डिलीशन के बिना दो स्ट्रिंग्स को एनाग्राम बनाने के लिए न्यूनतम मैनिपुलेशन

    मान लीजिए हमारे पास समान लंबाई की दो स्ट्रिंग्स हैं, हमें बिना किसी कैरेक्टर को डिलीट किए दो स्ट्रिंग्स को एनाग्राम बनाने के लिए आवश्यक न्यूनतम परिवर्तनों की संख्या ढूंढनी है। एनाग्राम दो स्ट्रिंग्स होती हैं जिनमें कैरेक्टर्स का समान सेट होता है। मान लीजिए दो स्ट्रिंग्स HELLO और WORLD हैं, यहां आवश्