Posted: 5 Mar, 2021
Difficulty: Moderate


Try Problem

Ninja is thinking of developing a game based on “Teen Patti” where a user will be provided with some number “N” or in technical term with an array “ARR[i]” and the user has to find the maximum number of triplets of indices (i, j, k) such that “BITWISE AND” of “ARR[i] & ARR[j] & ARR[K]” is ‘0’.

Help our Ninja to write a code for developing a game so that he is able to check that the user is giving a correct answer or not.

So your task is to count the maximum number of triplets indices (i, j, k) in a given array such that “ARR[i] & ARR[j] & ARR[k]” is ‘0’ where “&” represents the Bitwise And Operator.

Input Format:

The first line of input contains a ‘T’ number of test cases.

The second line of each test case contains ‘N’ i.e size of the array.

The third line of each test case contains an array ‘ARR[i]’ containing ‘N’ number of values.

Output Format:

For each test case, return the maximum count of triplets indices.
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.


1 <= T <= 5
1 <= N <= 10^3
0 <= i, j, k <= N
1 <= A[i] <= 10^3

Time Limit: 1 sec
Approach 1
  • In this approach, we go through each and every triplet’s indices and check whether their ‘Bitwise And’ is ‘0’ or not.
  • So for this, we traverse through the array by running three nested loops so there will be three variables ‘i’, ‘j’, ‘k’. ‘I’ is the variable from the first loop ‘j’ is the variable from the second loop and ‘k’ is the variable from the third loop.
  • So now we check:
    • If ‘ARR[i] & ARR[j] & ARR[k]’ or we can say ‘Bitwise And’ is ‘0’ we increase the count by ‘1’.
    • Else traverse the array further.
  • After traversing we return the count as our answer.
Try Problem