Find single number

Q&A's, tips, howto's
Locked
cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Find single number

Post by 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
Posts: 66
Joined: Sat Nov 09, 2013 8:49 pm

Re: Find single number

Post by fdb »

HI Cameyo,

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

Code: Select all

(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
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: Find single number

Post by 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
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: Find single number

Post by cameyo »

My solution using XOR:

Code: Select all

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

fdb
Posts: 66
Joined: Sat Nov 09, 2013 8:49 pm

Re: Find single number

Post by fdb »

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

Locked