Tricks in solving common programming problems

O(1)-space collision detection

At times, you need to detect for once whether a collision occurs. For example, you may need to enumerate a sequence$$ x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots $$until either a desired element is found or a cycle is detected. A naive method to detect a cycle requires storing all elements ever enumerated in a hash table. This method however would need to store the entire sequence in the worst case. Instead, you can utilize one of the cycle detection techniques to reduce the space to O(1) at the cost of possibly longer search time.

(more to come...)