How hard is LeetCode 982. Triples with Bitwise AND Equal To Zero?

LeetCode 982. Triples with Bitwise AND Equal To Zero is rated Hard on LeetCode.

What is the time complexity of LeetCode 982. Triples with Bitwise AND Equal To Zero?

The Python solution on this page runs in O(n^2 + n \times M).

What is the space complexity of LeetCode 982. Triples with Bitwise AND Equal To Zero?

The Python solution on this page uses 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 auxiliary space.

What topics does LeetCode 982. Triples with Bitwise AND Equal To Zero cover?

LeetCode 982. Triples with Bitwise AND Equal To Zero is tagged Bit Manipulation, Array and Hash Table on LeetCode.

Triples with Bitwise AND Equal To Zero — LeetCode 982 Python Solution

HardBit ManipulationArrayHash Table

Problem: #982
Pattern: Bit Manipulation
Reading time: 2 min
Source: leetcode.com

The problem

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

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

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(n^2 + n \times M)
Space	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 auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 982. Triples with Bitwise AND Equal To Zero is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 982. Triples with Bitwise AND Equal To Zero?: LeetCode 982. Triples with Bitwise AND Equal To Zero is rated Hard on LeetCode.
What is the time complexity of LeetCode 982. Triples with Bitwise AND Equal To Zero?: The Python solution on this page runs in O(n^2 + n \times M).
What is the space complexity of LeetCode 982. Triples with Bitwise AND Equal To Zero?: The Python solution on this page uses 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 auxiliary space.
What topics does LeetCode 982. Triples with Bitwise AND Equal To Zero cover?: LeetCode 982. Triples with Bitwise AND Equal To Zero is tagged Bit Manipulation, Array and Hash Table on LeetCode.