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

बिटवाइज AND शून्य के बराबर वाले ट्रिपलेट C++ में

मान लीजिए हमारे पास पूर्णांकों की एक सरणी A है। हमें सूचकांकों (i, j, k) के उन ट्रिपलेट्स की संख्या ढूंढनी है जहां 0 <= i, j, k < A का आकार और A[i] AND A[j] AND A[k] == 0, जहां AND बिटवाइज-AND ऑपरेटर दर्शाता है।

उदाहरण के लिए, यदि इनपुट [3,1,2] है, तो आउटपुट 12 होगा।

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

हम सभी जोड़ियों के AND परिणामों को पूर्व-गणना करके फिर तीसरे तत्व के साथ जांच करते हैं:

  • सभी जोड़ियों (i, j) के लिए A[i] & A[j] की आवृत्ति की गणना करें

  • प्रत्येक तत्व x = A[i] के लिए, मैप में सभी कुंजियों के माध्यम से पुनरावृति करें

  • यदि (कुंजी & x) == 0, तो इसकी आवृत्ति को उत्तर में जोड़ें

  • यह O(n^2) को O(n^2 + n * अद्वितीय_जोड़ी_मान) तक कम करता है

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int countTriplets(vector<int>& A){ 
        unordered_map<int, int> m; 
        int ret = 0; 
        int n = A.size(); 
        
        // सभी जोड़ियों के AND की गणना करें
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) { 
                m[A[i] & A[j]]++; 
            } 
        } 
        
        // तीसरे तत्व के साथ जांचें
        for (int i = 0; i < n; i++) { 
            int x = A[i]; 
            for (auto& a : m) { 
                if ((a.first & x) == 0) { 
                    ret += a.second; 
                } 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {3,1,2}; 
    cout << (ob.countTriplets(v)); 
    return 0;
}

इनपुट

{3,1,2}

आउटपुट

12
  1. - C++ में संख्या N का बिटवाइज AND सेट प्रिंट करें

    इस समस्या में, हमें 0 से n तक की उन सभी संख्याओं को प्रिंट करना है जो n के बाइनरी के बिटवाइज AND हैं। आइए एक उदाहरण लेकर अवधारणा को बेहतर ढंग से समझते हैं। Input : N = 4. Output : 0 4 Explanation : 0 & 4 = 0 1 & 4 = 0 2 & 4 = 0 3 & 4 = 0 4 & 4 = 4. Input : N =

  1. - C++ में N से छोटी या बराबर न्यूनतम संख्याएं जिनका योग S हो

    समस्या कथन1 से N तक N संख्याएं और एक संख्या S दी गई है। कार्य उन न्यूनतम संख्याओं को प्रिंट करना है जिनका योग S देता हैउदाहरणयदि n = 7 और s = 10 तो न्यूनतम 2 संख्याएं आवश्यक हैं(9, 1) (8, 2) (7, 3) (6, 4)एल्गोरिदमउत्तर की गणना नीचे दिए गए सूत्र का उपयोग करके की जा सकती है (S/N) + 1 यदि { S %N > 0

  1. - C++ में बिटवाइज़ AND क्या है?

    बिटवाइज़ AND ऑपरेटर (&) पहले ऑपरेंड के प्रत्येक बिट की तुलना दूसरे ऑपरेंड के संबंधित बिट से करता है। यदि दोनों बिट्स 1 हैं, तो संबंधित परिणाम बिट 1 सेट होता है। अन्यथा, संबंधित परिणाम बिट 0 सेट होता है। बिटवाइज़ इन्क्लूसिव AND ऑपरेटर के दोनों ऑपरेंड्स इंटीग्रल प्रकार के होने चाहिए। उदाहरण के लि