Triples With Bitwise And Equal To Zero - Leetcode Solution

Problem Statement:

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

• 0 <= i < j < 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: (i=0, j=0, k=1) : 2 & 2 & 1 (i=0, j=1, k=1) : 2 & 1 & 1 (i=0, j=1, k=2) : 2 & 1 & 3 (i=0, j=2, k=2) : 2 & 3 & 3 (i=1, j=1, k=2) : 1 & 1 & 3 (i=1, j=2, k=2) : 1 & 3 & 3

Approach:

Since the constraint has already been given in the question that the length of the array, nums, will not exceed 3000, we can make use of this property and apply a brute force approach. We can iterate through all possible triples (i, j, k) satisfying the above conditions and check if the Bitwise And of these three numbers equals 0. We increment the count variable every time such an occurrence occurs. In order to implement this approach, we need to use 3 nested loops, which in the worst case would lead to a time complexity of O(n^3), which is not efficient enough for large Test Cases.

In order to optimize this solution, we need to break down the problem into smaller subproblems. One such approach can be to make use of Bit Manipulation and Dynamic Programming. We first need to count the frequency of occurrence of each number in the given nums array. This can be done easily using a HashMap.

We then create a 2D DP Array of length N x (1<<M) where N is the length of the array, and M is the total number of bits in the maximum number present in the given array. The value DP[i][mask] represents the number of combinations of (i, j) such that the bitwise AND of nums[i] and nums[j] equals mask. For example, DP[0][1] would represent the number of possible combinations (0, j) in the subarray nums[1, N] such that nums[0] & nums[j] = 1 If we are able to populate this DP array, we can simply use the formula nCr(n, 3) for the final answer.

We can do that by applying a bottom-up approach. We start by finding out the number of pairs (i, j) such that nums[i] & nums[j] equals a given mask. This can be obtained by iterating over all the numbers in the array and for every number nums[i], we try corresponding with every other number nums[j] in the array. Since we already have the frequency of occurrence of each element, we can directly use it to compute the number of pairs in constant time. Once the number of pairs have been computed for a given mask and a given index (i), the same can be stored in the DP[i][mask] position. Now, once we have computed the entire DP array, we can use the same formula mentioned above and compute the final answer.

Time Complexity: O(N x 2^M + N^2 M) where N is the length of the array, and M is the total number of bits in the maximum number present in the given array.

Solution:

class Solution {
    public int countTriplets(int[] nums) {
        HashMap<Integer, Integer> freq = new HashMap<>(); //store frequency of each number
        int n = nums.length;
        int ans = 0;

        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        int m = 0;
        for (int num : nums) {
            m = Math.max(m, num);
        }

        int[][] DP = new int[n][1 << 16];

        //bottom-up dp through all the numbers in the array
        for (int i = n - 1; i >= 0; i--) {
            for (int mask = 0; mask <= m; mask++) {
                int pairs = DP[i][mask ^ m] + freq.getOrDefault(mask, 0);

                if (i + 1 < n) {
                    pairs += DP[i + 1][mask];
                }

                DP[i][mask] = pairs;
            }
        }

        //final calculation using the DP array
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int mask = nums[i] & nums[j];
                ans += DP[j + 1][mask];
            }
        }

        return ans;
    }
}

1