# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 i^{th} position of the resulting bit pattern is computed from the i^{th} 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 ≤ 10 ^{5} )**, the size of the array

Output one integer, the answer to Imam’s problem.

Input | Output |
---|---|

3 1 2 3 | 3 |

Input | Output |
---|---|

4 1 2 2 3 | 5 |

81% Solution Ratio

Bishal_GEarliest,

ASM_ATIKURFastest, 0.0s

protapLightest, 524 kB

mdvirusShortest, 258B

Login to submit

If we use bit-wise exclusive-or operators that are available in most of the languages and compare al... Read more...