All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

SPECIAL PAIRS
Tag(s):

Bitmask, Dynamic Programming, Hard

Problem
Editorial
Analytics

You have been given an integer array A on size N. You must report the number of ordered pairs (i,j) such that A[i] & A[j] is zero.
Here '&' denotes the BITWISE AND.
(i,j) and (j,i) are considered different.

Input
First line contains T-Number of Test cases. First line of each test contains N. Next line contains N integers - the i'th integer A[i].
Output
Output the number of such pairs for each test case.

Constraints
T ≤ 10
N ≤ 100000
A[i] ≤ 1000000

SAMPLE INPUT
1
5
41 47 34 40 29 
SAMPLE OUTPUT
2
Explanation

These are the required pairs 3 5 5 3

Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Hewlett Packard

Challenge Name

Think-A-Thon

Notifications
View All Notifications

?