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)).
HI Cameyo,
I would do something like this, using a hash table:
(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
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
My solution using XOR:
(find-number '(1 3 1 2 3 4 5 2 4))
;-> 5
Very nice! An instruction I've never used in practice.