By not reading the input again and just keeping the n-bit counter in unrelated memory, since the actual input is kind of irrelevant for this, only its size. Again, may or may not apply depending on what precisely they meant by a "fixed" additional amount of memory...

Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).