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

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

समस्या कथन

एक सरणी "arr" दी गई है, सरणी को अच्छा बनाने के लिए हटाए जाने वाले न्यूनतम तत्वों की संख्या ढूंढें।

एक अनुक्रम a1, a2, a3...an को अच्छा कहा जाता है यदि प्रत्येक तत्व a[i] के लिए, एक तत्व a[j] (i ≠ j) मौजूद होता है जैसे कि a[i] + a[j] 2 की घात हो।

arr1[] = {1, 1, 7, 1, 5}

उपरोक्त सरणी में यदि हम तत्व '5' को हटा दें तो सरणी अच्छी सरणी बन जाती है। इसके बाद arr[i] + arr[j] का कोई भी जोड़ा 2 की घात होता है:

  • arr[0] + arr[1] = (1 + 1) = 2 जो 2 की घात है
  • arr[0] + arr[2] = (1 + 7) = 8 जो 2 की घात है

एल्गोरिदम

1. हमें केवल ऐसे a[i] को हटाना है जिनके लिए कोई a[j] नहीं है जैसे कि a[i] + a[j] 2 की घात है।
2. प्रत्येक मान की सरणी में घटनाओं की संख्या ढूंढें
3. जांचें कि a[i] का कोई जोड़ा a[j] नहीं है

C++ उदाहरण

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

int minDeleteRequred(int *arr, int n) {
    map<int, int> frequency;
    for (int i = 0; i < n; ++i) frequency[arr[i]]++;
    
    int delCnt = 0;
    for (int i = 0; i < n; ++i) {
        bool doNotRemove = false;
        for (int j = 0; j < 31; ++j) {
            int pair = (1 << j) - arr[i];
            if (frequency.count(pair) && 
                (frequency[pair] > 1 || (frequency[pair] == 1 && pair != arr[i]))) {
                doNotRemove = true;
                break;
            }
        }
        if (!doNotRemove) ++delCnt;
    }
    return delCnt;
}

int main() {
    int arr[] = {1, 1, 7, 1, 5};
    cout << "Minimum elements to be deleted = " << minDeleteRequred(arr, SIZE(arr)) << endl;
    return 0;
}

आउटपुट

Minimum elements to be deleted = 1
  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++ में ऐरे में न्यूनतम संख्या जोड़कर योग को सम बनाना

    मान लीजिए एक ऐरे है जिसमें कुछ संख्याएं हैं। हमें बताना है कि न्यूनतम कितनी संख्याएं जोड़ने से तत्वों का योग सम हो जाएगा। संख्या 0 से बड़ी होनी चाहिए। इसलिए यदि तत्वों का योग विषम है, तो हम 1 जोड़ेंगे, लेकिन यदि योग पहले से सम है, तो हम 2 जोड़कर इसे सम बनाएंगे। एल्गोरिदम addMinNumber(arr) begin