1332. Count of Pairs with AND Equal to Zero

Given an array of non-negative integers, count the index pairs (i, j) with i < j whose bitwise AND is zero, meaning the two values share no set bit.

Input: A JSON object {"nums": [<non-negative integers>]}.

Output: Return the number of pairs whose AND equals 0.

Examples

Input: {"nums":[1,2,4]}
Output: 3
Explanation: Every pair uses distinct bits -> 3.

Input: {"nums":[3,3]}
Output: 0
Explanation: 3 AND 3 = 3, not zero -> 0.

Constraints

• 1 <= len(nums) <= 2000
• 0 <= nums[i] < 2^16

Asked by