TEEN PATTI

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
11 upvotes
Asked in company
Flipkart limited

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.
Note: 
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Constraints:

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

Time Limit: 1 sec

Sample Input 1:

2
3
2 1 3
3
21 15 6

Sample Output 1:

12
0

Explanation of Sample Input 1:

Test Case 1:

In the first line, there is the number of test cases i.e., ‘2’, and in the next line ‘3’is the size of the array. In the third line elements of the array are given {2,1, 3} so now we try to find i, j, k such that Bitwise And is ‘0’.
(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
So there were 12 such triplets whose Bitwise And is ‘0’ hence the output is ‘12’.


Test Case 2:

For this test case, the array is {21, 15, 6} so there are no triplet indices such that Bitwise And is ‘0’. Hence the output is ‘0’.

Sample Input 2:

2
3
1 1 1
3
2 2 1

Sample Output 2:

0
18
Hint

Try to calculate bitwise and of every triplets using multiple for loops.

Approaches (2)
Brute Force
  • 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.
Time Complexity

O(N^3), where ‘N’ is the size of an array.

 

As three nested loops were running.

Space Complexity

O(1), 

 

We are using constant space.

Code Solution
(100% EXP penalty)
TEEN PATTI
Full screen
Console