First of all, Newsflash! that's illegal in a programming interview, please solve this question using a whiteboard instead, show a mathematical proof if needed.
/s