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

C++ में सरणी के सभी तत्वों को हटाने के लिए आवश्यक न्यूनतम ऑपरेशन

समस्या कथन

एक पूर्णांक सरणी arr दी गई है, सरणी के सभी तत्वों को हटाने के लिए आवश्यक न्यूनतम ऑपरेशन की संख्या प्रिंट करें। तत्व हटाते समय निम्न प्रतिबंध है:

  • सरणी से किसी भी तत्व को यादृच्छिक रूप से चुना जा सकता है और उससे विभाज्य हर तत्व को सरणी से हटाया जा सकता है

यदि arr[] = {2, 4, 15, 10, 8, 5, 3}, तो सभी तत्वों को हटाने के लिए 3 ऑपरेशन आवश्यक हैं:

  • यदि हम 2 चुनते हैं तो यह {2, 4, 10, 8} हटा देगा
  • यदि हम 5 चुनते हैं तो यह {5, 15} हटा देगा
  • यदि हम 3 चुनते हैं तो यह {3} हटा देगा

एल्गोरिदम

1. सरणी को आरोही क्रम में सॉर्ट करें और प्रत्येक तत्व की घटनाओं को गिनें
2. शुरुआत से प्रत्येक अनमार्क्ड तत्व के लिए, चुने गए तत्व से विभाज्य सभी तत्वों को मार्क करें, और परिणाम काउंटर बढ़ाएं

C++ उदाहरण

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;

int getMinOperations(int *arr, int n) {
    int map[MAX] = {0};
    sort(arr, arr + n);
    for (int i = 0; i < n; ++i)
        map[arr[i]]++;
    
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (map[arr[i]]) {
            for (int j = i; j < n; ++j) {
                if (arr[j] % arr[i] == 0)
                    map[arr[j]] = 0;
            }
            ++cnt;
        }
    }
    return cnt;
}

int main() {
    int arr[] = {2, 4, 15, 10, 8, 5, 3};
    cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
    return 0;
}

आउटपुट

Minimum required operations = 3
  1. - C++ में सरणी में एक संख्या की फ्रीक्वेंसी ज्ञात करना

    मान लीजिए हमारे पास एक सरणी है। इसमें n अलग-अलग तत्व हैं। हमें सरणी में एक तत्व की फ्रीक्वेंसी जांचनी है। मान लीजिए A = [5, 12, 26, 5, 3, 4, 15, 5, 8, 4], यदि हम 5 की फ्रीक्वेंसी ढूंढने की कोशिश करते हैं, तो यह 3 होगी। इसे हल करने के लिए, हम सरणी को बाएं से स्कैन करेंगे, यदि तत्व दी गई संख्या के सम

  1. - C++ का उपयोग करके सरणी में ऐसा तत्व खोजें जिससे सभी तत्व विभाज्य हों

    मान लीजिए हमारे पास कुछ तत्वों के साथ एक सरणी A है। हमें A से एक ऐसा तत्व ढूंढना है जिससे सभी तत्व इससे विभाज्य हों। मान लीजिए A = [15, 21, 69, 33, 3, 72, 81] है, तो तत्व 3 होगा, क्योंकि सभी संख्याएं 3 से विभाज्य हैं। इस समस्या को हल करने के लिए, हम A में सबसे छोटी संख्या लेंगे, फिर जांचेंगे कि क्य

  1. - C++ में ऐरे के सभी एलिमेंट्स को समान बनाने के लिए न्यूनतम डिलीट ऑपरेशन्स

    समस्या कथनn एलिमेंट्स का एक ऐरे दिया गया है जैसे कि एलिमेंट्स रिपीट हो सकते हैं। हम ऐरे से किसी भी संख्या में एलिमेंट्स डिलीट कर सकते हैं। कार्य ऐरे को समान बनाने के लिए डिलीट किए जाने वाले एलिमेंट्स की न्यूनतम संख्या ढूंढना है।arr[] = {10, 8, 10, 7, 10, -1, -4, 12}सभी ऐरे एलिमेंट्स को समान बनाने के