C++에서 Bitwise AND Equal To Zero를 사용한 트리플

<시간/>

정수 A의 배열이 있다고 가정합니다. 다음과 같은 인덱스(i, j, k)의 트리플 수를 찾아야 합니다. -

0 <=i
0 <=j
0 <=k

A[i] AND A[j] AND A[k]는 0이며, 여기서 AND는 비트 AND 연산자를 나타냅니다.

따라서 입력이 [3,1,2]와 같으면 출력은 12

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −
하나의 맵 정의
ret :=0
n :=A의 크기
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - j 초기화의 경우:=0, j
initialize i :=0의 경우, i
- x :=A[i]
- 모든 키-값 쌍에 대해 m
  - (a.key AND x)가 0과 같으면 -
    - ret :=ret + a.value
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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();
      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;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,2};
   cout << (ob.countTriplets(v));
}

입력

{3,1,2}