Given a pile of
npairs of socks, containing
2nelements (assume each sock has exactly one matching pair), what is the best way to pair them up efficiently with up to logarithmic extra space?
I like this answer from Srinivas, although it assumes that each sock has more than one pair:
I use pigeon hole principle to pair exactly one from the laundry pile. I have 3 different colors of socks (Red, Blue and Green) and 2 pairs of each color. I pick up 4 number of socks each time and I always make up a pair and get to work.