2

Eräs tapa on järjestää alkiot ja katsoa, onko alkio A[i] eri kuin
sen vierekkäiset alkiot.

yksinaiset(A)
  sort(A)      // Mikä tahansa O(n log n) järjestämisalgoritmi.
               // QuickSort on pahimmassa tapauksessa O(n^2),
               // jos jakoalkion valinta menee huonosti.

  if n == 0:
    return 0
  else if n == 1:
    return 1
  else if n == 2:
    if A[0] < A[1]:
      return 2
    else
      return 0
  else:
    yksinaiset = 0
    if A[0] < A[1]:
      yksinaiset += 1
    
    for i in 2 to n - 1:
      if A[i - 1] < A[i] and A[i] < A[i + 1]:
        yksinaiset += 1
    
    if A[n-1] < A[n]:
      yksinaiset += 1

    return yksinaiset



Eräs toinen tapa on käyttää hakupuita.
HashMapista hakeminen ei ole välttämättä O(log n),
jos hajautusfunktio toimii huonosti.

yksinaiset(A)
  yksinaiset := new TreeSet
  liikaa := new TreeSet
  
  for i in 1 to n:
    if yksinaiset.contains(A[i]):
      yksinaiset.remove(A[i])
      liikaa.add(A[i])
    else if !liikaa.contains(A[i]):
      yksinaiset.add(A[i])

  return yksinaiset.size()



Pienistä koodausvirheistä, kuten erikoistapauksien unohtamisesta
tai quicksortin/hashmapin käyttämisestä ilman huomautusta niiden mahdollisista
ongelmista menetti yhden pisteen.