Last Updated: 5 Mar, 2021
TEEN PATTI
Moderate
Asked in company
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.
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
Approaches
- 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.
- Now in this approach, we use the unordered map/dictionary for optimizing the brute force. So in brute force, we are simply traversing our array with the help of three nested loops but in this approach, we declared an unordered map named 'TUPLES' which can store two integer values.
- So now we traverse our array with two nested loops and store there ‘Bitwise And’ in the map in its first integer.
- Now we once again traverse the array if the ‘Bitwise And’ of integer stored in the map and now with the element of the array is ‘0’, we increment our 'ANS'.
- So in this way with the help of using the map as a data structure time complexity decreases.
- After traversing the array we return the 'ANS'.
Similar problems