Technical Interviews: More Than a Brain Teaser?

If the interview is irritated they're not doing it right. In my case I'd just ask the interviewee to explain his or her answer, and if it holds up, make sure to write in the report to the hiring committee that nobody else I interviewed came up with this answer before. That's why it's an interview and not a standardized test.

Coming up with an unusual solution should be a win, though it's of course not required.

Also, in some cases I might ask a slightly harder follow-up where the shortcut doesn't work.

The point is to show off your thinking process. So if you answer with that, how does that show any thinking? It's not like the interviewer really needs the algorithm for Gray codes, so I'm not sure how rattling off an efficient but opaque solution helps anyone. They're not evaluating your memorization abilities.