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

C++ में XOR को अधिकतम बनाने के लिए हटाए जाने वाले न्यूनतम तत्व

समस्या कथन

एक संख्या N दी गई है। 1 से N के बीच के न्यूनतम तत्वों की संख्या ढूंढें जिन्हें हटाया जाए ताकि शेष तत्वों से प्राप्त XOR अधिकतम हो।

एल्गोरिदम

1. यदि n 1 या 2 है तो किसी तत्व को हटाने की आवश्यकता नहीं है। उत्तर शून्य है।
2. एक संख्या ढूंढें जो 2 की घात है और n से बड़ी या बराबर है। इसे nextNumber कहें।
   2.1. यदि n == nextNumber या n == (nextNumber - 1) तो उत्तर 1 है
   2.2. यदि n == (nextNumber - 2) तो उत्तर 0 है
3. यदि n सम है तो उत्तर 1 अन्यथा 2

C++ उदाहरण

#include <iostream>
using namespace std;

int nextPowerOf2(int n) {
    if (n && !(n & (n - 1))) return n;
    int cnt = 0;
    while (n) { n /= 2; ++cnt; }
    return (1 << cnt);
}

int elmentsToBeRemoved(int n) {
    if (n == 1 || n == 2) return 0;
    int nextNumber = nextPowerOf2(n);
    if (n == nextNumber || n == nextNumber - 1) return 1;
    else if (n == nextNumber - 2) return 0;
    else if (n & 1) return 2;
    else return 1;
}

int main() {
    int n = 10;
    cout << "Numbers to be removed = " << elmentsToBeRemoved(n) << endl;
    return 0;
}

आउटपुट

Numbers to be removed = 1
  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++ में स्ट्रिंग को पालिंड्रोम बनाने के लिए न्यूनतम विलोपन

    समस्या कथन आकार n की एक स्ट्रिंग दी गई है। स्ट्रिंग को पालिंड्रोम बनाने के लिए न्यूनतम वर्णों को हटाने का कार्य है। यदि दी गई स्ट्रिंग abcda है, तो हम पहले और अंतिम को छोड़कर किन्हीं 2 वर्णों को हटा सकते हैं ताकि यह पालिंड्रोम बन जाए। यदि हम b और c हटाते हैं तो ada स्ट्रिंग पालिंड्रोम है यद

  1. - C++ में किसी संख्या के गुणनखंडों का न्यूनतम योग ढूंढना

    यहां हम देखेंगे कि किसी दी गई संख्या के गुणनखंडों का न्यूनतम योग कैसे प्राप्त करें। मान लीजिए एक संख्या 12 है। हम इसे अलग-अलग तरीकों से गुणनखंडित कर सकते हैं: 12 = 12 × 1 (12 + 1 = 13) 12 = 2 × 6 (2 + 6 = 8) 12 = 3 × 4 (3 + 4 = 7) 12 = 2 × 2 × 3 (2 + 2 + 3 = 7) न्यूनतम योग 7 है। हम