FRND - FRIENDSHIP!!!


Q[b] has recently been visited by extraterrestrials from planet Quan_Lank , where everyone’s name is a positive integer. All residents of the planet know each other. Two Quan_Lank-ians calculate the strength of their friendship by converting their names to binary, aligning them one under the other, and writing a digit in each column: 0 if the two binary digits in that column are equal, 1 if they differ. The binary result is then converted back to the decimal system.

For example, the friendship value of 19 and 10 equals 25:

1   0   0   1   1 = 19

0   1   0   1   0 = 10

-------------------

1   1   0   0   1 = 25

 

The value of a planet in the Universe is defined as the sum of all friendship values. Q[b] has asked you to help him compute the value of planet Quan_Lank!

 

INPUT

The first line of input contains the positive integer N (the number of residents of planet Quan_Lank , 1<=N<=10^6).
The next N lines contain the names of residents - positive integers smaller than 10^6, one per line.

OUTPUT

The only line of output must contain the value of planet Quan_Lank.

SAMPLE

Input
2
19
10
Output
25

Input

3
7
3
5
Output
12

Second sample description: The friendship value of residents 1 and 2 equals 4, for residents 1 and 3
it equals 2, and for residents 2 and 3 it equals 6. The solution is 4 + 2 + 6 = 12.


hide comments
minhhoa_tr: 2018-10-02 05:20:52

Someone who failed at 10th testcase please print %lld for the result

shahi9935: 2018-06-24 07:27:15

100th :-)

sagar_zhcet: 2017-06-24 13:43:58

nice question
learned a lot about bits...

siddharth_0196: 2017-05-16 14:07:50

pow(2,i) --> WA
(1<<i) -->AC

aeonflux: 2017-02-15 21:47:59

too easy!

prakash: 2017-01-30 20:03:59

easy one use long long for power computation also

poda_venna: 2016-08-11 15:11:47

array of bitset leads to RTE

zany: 2016-08-03 21:26:32

submitted code in C++ A.C same code in python giving TLE!

mkfeuhrer: 2016-06-22 21:38:55

very good ques.!! bit but u have to think more than a bit :-P

fly_sky12: 2016-05-11 15:21:06

getting wrong answer in 10th test case :(
though I used unsigned long long int

Last edit: 2016-05-11 15:21:50

Added by:BLANKRK
Date:2014-01-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64