home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

จำนวนทริปเปิลที่ Bitwise AND เท่ากาศูนย์ใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A หาจำนวนทริปเปิล (i,j,k) ที่ 0≤i,j,k

ตัวอย่าง

A = [3,1,2] → Output: 12

แนวทางแก้ปัญหา: Precompute Pair AND + Lookup

  1. คำนวณความถี่ของ A[i] & A[j] สำหรับทุกคู่ (i,j) → เก็บใน map m
  2. สำหรับแต่ละ x = A[k] หาผลรวม m[val] สำหรับทุก val ที่ val & x == 0

เหตุผลที่ทำงานได้

(A[i] & A[j] & A[k]) == 0 ⇔ ((A[i] & A[j]) & A[k]) == 0
ให้ pair_and = A[i] & A[j] ต้องการ pair_and & A[k] == 0

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int countTriplets(vector<int>& A) {
        unordered_map<int,int> m;
        int n = A.size();
        
        // Precompute all pair ANDs
        for(int i=0; i

ความซับซ้อน

  • เวลา: O(n² + n × |m|) โดย |m| ≤ 2¹⁶ = 65536 (เพราะ A[i] ≤ 2¹⁶-1 ในโจทย์ต้นฉบับ)
  • พื้นที่: O(|m|) ≤ O(2¹⁶)