Imam has been participating in online programming contests for years. His goal is to become a “Master” in a popular contest site. He realizes that in order to achieve his target, he needs mastery in many different topics. So he decides to master the skill of XOR operations.
XOR is a bitwise operation that is performed on two bit patterns of equal length. Bit patterns are strings that only contain 0 or 1. The XOR operation results a single bit pattern, the length of which is equal to the length of the two given patterns. The ith position of the resulting bit pattern is computed from the ith position of both the given patterns. The resulting value of position i is 1, if just one of the values of the given patterns in that position is 1. Otherwise, the resulting value is 0.
For example, let’s say we have two given patterns X and Y. X consists of a 3-length bit pattern “101” and Y also has a 3-length bit pattern “001”. So the resulting bit pattern will be:
101 XOR 001 = 100
Any integers can be converted into a bit pattern by converting them in base 2. Any set of integers can be converted into bit patterns of same length, possibly by adding leading zeros. In the above example, X=101 represents integer 5 in binary form. For, Y=001, integer 1 is represented in a 3-bit pattern by appending additional zeros at the leading positions.
After studying all of the above, Imam has come up with an interesting problem involving XOR operations. The problem states: “Given an array A of integers of size N, you have to count the number of pairs ( i, j ) ( 1 ≤ i ≤ j ≤ N ) for which A[i] XOR A[j] will contain at least one 1 in it’s resulting pattern.” Here. A[i] and A[j] are bit patterns of the array A at position i and j respectively. Bit patterns of each position can be found after converting the numbers of that position in binary.
Imam usually comes up with brilliant problem ideas, but he fails to write solutions for them. Thus, his problems are always rejected in major contests. Your task is to help Imam to write an efficient solution for this problem.
The first line of the input contains an integer N ( 1 ≤ N ≤ 105 ), the size of the array A. The next N lines contain one integer each, the elements of the array A in sequential order. Each of the elements of array A will be non-negative and may have the maximum value of 109.
Output one integer, the answer to Imam’s problem.
3 1 2 3
4 1 2 2 3
Login to submit
If we use bit-wise exclusive-or operators that are available in most of the languages and compare al... Read more...