@ashiqimran perfectly working solution. But if it was expected of me to come up with this during an interview, I would prefer to stay away from that team. It's like expecting to come up with KMP algorithm on the spot :-)
Yeah, I don't agree either. If n=0, then, since "...n representing the total number of bits in the code..", every element of the gray code sequence needs to have length 0. So yes, even though the question says every gray code starts with zero, the gray code for n=0, meaning , does trivially start with zero since it has no length. That test case should be changed.