U teoriji informacija, Hemingovo rastojanje (eng. Hamming distance) između dva stringa jednakih dužina je broj pozicija na kojima se odgovarajući simboli razlikuju. Drugim rečima, ovo rastojanje meri minimalni broj zamena potrebnih za transformaciju jednog stringa u drugi.

U zadatku ćemo posmatrati 32-bitne brojeve, gde se Hemingovo rastojanje ham(a, b) računa kao broj bitova na kojima se brojevi a i b razlikuju. Na primer, Hemingovo rastojanje za brojeve 93 = 00...001011101 i 75 = 00...001001011 je 3, pošto se brojevi razlikuju na drugom, trećem i petom bitu s desna.

Dat je niz celih brojeva a dužine n. Odrediti zbir Hemingovih rastojanja svih parova elemenata niza, odnosno

∑_{i < j} ham(a[i], a[j]).

Ulaz:

(Ulazni podaci se učitavaju iz datoteke sumhem.in.) U prvom redu se nalazi prirodan broj n (1 < n < 100.000). U sledećih n redova se nalazi po jedan broj i oni predstavljaju niz a (0 < a[i] < 2 ³¹ - 1).

Izlaz:

(Izlazni podaci se ispisuju u datoteku sumhem.out.) U prvom i jedinom redu ispisati sumu Hemingovih rastojanja svaka dva broja u nizu.

Primer:

4
1
9
4
10

14

Objašnjenje.

Hemingova rastojanja za svaki par brojeva iz niza su jednaka ham(1, 9) = 1, ham(1, 4) = 2, ham(1, 10) = 3, ham(9, 4) = 3, ham(9, 10) = 2 i ham(4, 10) = 3. Suma svih rastojanja je upravo 14.

Primer:

7
128
7
0
99
18
10
1984

84

Napomena.

U 40% test primera, broj n će biti manji od 3.000.

/*
  Problem: Dat je niz a duzine n <= 100.000 prirodnih brojeva manjih od 2^31. 
  Naci sumu Hemingovih rastojanja svaka dva broja a [i] i a [j], gde je i < j.
  Hemingovo rastojanje za dva broja se definise kao broj bitova na kojima se ti brojevi razlikuju.

  Resenje: Kvadratno resenje u O (32 n^2) donosi 40 poena. 
  Za linearno resenje O (32 n) je potrebno primetiti da svaki bit mozemo posmatrati nezavisno.
  Za i-ti bit, 0 <= i <= 31, neka count predstavlja koliko brojeva imaju 1 na i-toj poziciji.
  Tada na ukupnu sumu dodajemo tacno count * (n - count).
  U resenju koristimo neoznacene brojeve sa 64 bita i idemo do bita najvece tezine.

  Autor: Aleksandar Ilic
*/

#include <stdio.h>
#define MAXN 100001

unsigned int a [MAXN];
int n;
long long sum;

long long check ()
{
  long long sum = 0;  
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
    {
      unsigned int x = a [i] ^ a [j];
      while (x > 0)
      {
        sum++;
        x = x & (x - 1);
      }
    }
  return sum;
}

int main ()
{
  FILE *in = fopen ("sumhem.in", "r");
  fscanf (in, "%d", &n);
  for (int i = 0; i < n; i++)
    fscanf (in, "%d", &a [i]);
  fclose (in);
  
  int max = a [0];
  for (int i = 0; i < n; i++)
    if (max < a [i])
      max = a [i];
  int max_bit = 1;
  while ((max_bit < 32) && (max > (1 << max_bit)))
    max_bit++;

  sum = 0;
  unsigned int pow = 1;
  for (int i = 0; i < max_bit; i++)
  {
    int count = 0;
    for (int j = 0; j < n; j++)
      if ((a [j] & pow) != 0)
        count++;
    sum = sum + (long long)count * (long long)(n - count);
    pow = pow << 1;
  }
  //printf ("%lld %lld\n", sum, check ());

  FILE *out = fopen ("sumhem.out", "w");
  fprintf (out, "%lld\n", sum);
  fclose (out);
  return 0;
}