Skip to content

Latest commit

 

History

History
199 lines (163 loc) · 4.72 KB

README_EN.md

File metadata and controls

199 lines (163 loc) · 4.72 KB
comments difficulty edit_url tags
true
Hard
Bit Manipulation
Array
Hash Table

982. Triples with Bitwise AND Equal To Zero

中文文档

Description

Given an integer array nums, return the number of AND triples.

An AND triple is a triple of indices (i, j, k) such that:

  • 0 <= i < nums.length
  • 0 <= j < nums.length
  • 0 <= k < nums.length
  • nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

 

Example 1:

Input: nums = [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

Example 2:

Input: nums = [0,0,0]
Output: 27

 

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < 216

Solutions

Solution 1: Enumeration + Counting

First, we enumerate any two numbers $x$ and $y$, and use a hash table or array $cnt$ to count the occurrences of their bitwise AND result $x &amp; y$.

Then, we enumerate the bitwise AND result $xy$, and enumerate $z$. If $xy &amp; z = 0$, then we add the value of $cnt[xy]$ to the answer.

Finally, we return the answer.

The time complexity is $O(n^2 + n \times M)$, and the space complexity is $O(M)$, where $n$ is the length of the array $nums$; and $M$ is the maximum value in the array $nums$, with $M \leq 2^{16}$ in this problem.

Python3

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        cnt = Counter(x & y for x in nums for y in nums)
        return sum(v for xy, v in cnt.items() for z in nums if xy & z == 0)

Java

class Solution {
    public int countTriplets(int[] nums) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        int[] cnt = new int[mx + 1];
        for (int x : nums) {
            for (int y : nums) {
                cnt[x & y]++;
            }
        }
        int ans = 0;
        for (int xy = 0; xy <= mx; ++xy) {
            for (int z : nums) {
                if ((xy & z) == 0) {
                    ans += cnt[xy];
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int countTriplets(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        int cnt[mx + 1];
        memset(cnt, 0, sizeof cnt);
        for (int& x : nums) {
            for (int& y : nums) {
                cnt[x & y]++;
            }
        }
        int ans = 0;
        for (int xy = 0; xy <= mx; ++xy) {
            for (int& z : nums) {
                if ((xy & z) == 0) {
                    ans += cnt[xy];
                }
            }
        }
        return ans;
    }
};

Go

func countTriplets(nums []int) (ans int) {
	mx := slices.Max(nums)
	cnt := make([]int, mx+1)
	for _, x := range nums {
		for _, y := range nums {
			cnt[x&y]++
		}
	}
	for xy := 0; xy <= mx; xy++ {
		for _, z := range nums {
			if xy&z == 0 {
				ans += cnt[xy]
			}
		}
	}
	return
}

TypeScript

function countTriplets(nums: number[]): number {
    const mx = Math.max(...nums);
    const cnt: number[] = Array(mx + 1).fill(0);
    for (const x of nums) {
        for (const y of nums) {
            cnt[x & y]++;
        }
    }
    let ans = 0;
    for (let xy = 0; xy <= mx; ++xy) {
        for (const z of nums) {
            if ((xy & z) === 0) {
                ans += cnt[xy];
            }
        }
    }
    return ans;
}