Why it expects [0] when the bits of Gray Code n equal to 0? I don't understand! Is there a code word with 0 bit?


  • 1
    I

    My submission came out with wrong answer with the following hints:

    Input:	0
    Output:	[]
    Expected:	[0]
    

    I think that 0 bit Gray Code can not form any code word, so the right answer should be [], but not [0], which, in my perspective, means there is one code word can be form when n = 0.
    Am I wrong?
    my code:

    class Solution {
    public:
        vector<int> grayCode(int n) {
    		vector<int> Gray;
    		if(n<1) return Gray;
    		Gray.push_back(0);
    		Gray.push_back(1);
    		for (int i = 1; i<n; ++i){
    			int len = Gray.size();
    			for (int j = len-1; j>=0; --j){
    				Gray.push_back(Gray[j]+ (1<<i));
    			}
    		}
    		return Gray;
        }
    };

  • 1
    S

    Please notice this statement in the description of the problem:

    A gray code sequence must begin with 0

    That means: no matter what value n takes, the gray code sequence must contain at least one element, aka 0, at the beginning.


  • 0
    I

    Oh, thanks! According to your answer, I searched Gray Code in Wikipedia, and the following statement is quoted from http://en.wikipedia.org/wiki/Gray_code.

    The one-bit Gray code is G1 = (0, 1). This can be thought of as built recursively as above from a zero-bit Gray code G0 = { Λ } consisting of a single entry of zero length.

    Now I understood that leetcode just replaces Λ with a zero. Even though it is mathematically wrong, it is good for the recursive definition.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.