# How to Pair Socks Efficiently

amit (via Jason Kottke):Given a pile of

`n`

pairs of socks, containing`2n`

elements (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.

## 2 Comments

[...] How to Pair Socks Efficiently (mjtsai.com) Share this:TwitterDiggGoogle +1StumbleUponFacebookRedditTumblrLinkedInPinterestLike this:LikeBe the first to like this. This entry was posted in Humor, List, Missing Sock List and tagged Bleach, Footwear, Humor, Laundry, Laundry Basket, List, Marilyn Monroe, Missing Sock List, Sock, Socks and Hosiery, Toe socks by dorothyadele. Bookmark the permalink. [...]

Stay up-to-date by subscribing to the Comments RSS Feed for this post.

I have a simpler solution.

1. Throw away all of your socks

2. Buy ~30 pairs of the same kind of socks

3. Have about three pairs of different sentinel socks

How to use:

1. Wear socks from big pile

2. If you can't find any of them anymore, switch to sentinel socks, wash your "big pile" socks

3. Go back to 1.

Works for me. No more stupid sock pairing.