Formatted question description: https://leetcode.ca/all/982.html

982. Triples with Bitwise AND Equal To Zero

Level

Hard

Description

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

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

Example 1:

Input: [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

Note:

  1. 1 <= A.length <= 1000
  2. 0 <= A[i] < 2^16

Solution

Use the idea of hash map, where the counts of each bitwise AND are stored. Since the numbers are in the range [0, 2^16) after bitwise AND operation, an array can be used instead of a hash map. The array map has length 2^16.

Loop over A. For each index pair (i, j) (where i and j can be in any order and it is possible that i == j), increase map[A[i] & A[j]] by 1. Then for each i from 0 to 2^16 - 1, if map[i] > 0, loop over A and for each j such that A[j] & i is 0, increase the number of triples by map[i].

Finally, return the number of triples.

class Solution {
    public int countTriplets(int[] A) {
        int tripletsCount = 0;
        int mapLength = 1 << 16;
        int[] map = new int[mapLength];
        int length = A.length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++)
                map[A[i] & A[j]]++;
        }
        for (int i = 0; i < mapLength; i++) {
            if (map[i] != 0) {
                for (int j = 0; j < length; j++) {
                    if ((A[j] & i) == 0)
                        tripletsCount += map[i];
                }
            }
        }
        return tripletsCount;
    }
}

All Problems

All Solutions