I got stuck for a little, then realized binary search would work--since you know the sequence and it's sorted, you know what the middle element should be. If the middle element is smaller than you expect, something's duplicated on the left side. Similarly if it's larger, then something's duplicated on the right. Keep going like this and you will eventually find the duplicate.