Find single number

[cameyo]

Given a list of positive integers each number appears twice except one number. Find the single number.

Note: The function has to traverse the list only once (O(n)).

[fdb]

HI Cameyo,



I would do something like this, using a hash table:

Code Select Expand


(define (find-number lst)
(define Myhash:Myhash)  ; hash table creation, O(1) lookup time
(set ' total 0)
(dolist (n lst)
(if (Myhash n)
(dec total n)    ; decrease when already added before
(begin
(Myhash n true)
(inc total n))))  ; if not in hash table increase
(delete 'Myhash)  ; first to delete contents and namespace
(delete 'Myhash)  ; second to delete symbol
total)

(find-number '(1 2 3 4 5 3 2 1 5))

-> 4


[cameyo]

Hi fdb,

thanks for your solution (hash table is nice).

There is a faster method using a boolean operator...

I'll post my solution in the next days.



cameyo

[cameyo]

My solution using XOR:

Code Select Expand

(define (find-number lst) (apply ^ lst))
(find-number '(1 3 1 2 3 4 5 2 4))
;-> 5

[fdb]

Very nice! An instruction I've  never used in practice.