मान लीजिए हमारे पास पूर्णांकों की एक सरणी 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