Why {0} for n=0?


  • 1
    S

    In my opinion, when n=0, the answer should be null. But the test data is {0}. I think it needs a better explanation. Except for this, the problem is okay.


  • 3

    Since we're supposed to return a list of integers, I'd say [0] is really the correct answer.

    Think of bit strings instead of numbers. For n=2, the answer could be ["00", "01", "11", "10"]. For n=1, it's ["0", "1"]. And for n=0, it is [""]. Not [] or even "null". There is a bit string of length zero. The empty string.

    Back to integers: What's the integer value of the empty bit string? For example for "101", the value is 1·22+0·21+1·20=5. Now if you do the same for the empty string, you get an empty sum, and the value of that is zero.


  • 0
    T

    Typo at for n=2 the second time.

    I disagree a little, I think the correct answer is []. Consider this: write down elements of the 0-bit Gray code immediately followed by the the elements of the 1-bit Gray code, followed by the 2-bit Gray code. I understand you would write "" | "0" "1" | "00" "01" "11" "10", but with numbers would you really write 0 | 0 1 | 00 01 11 10 or just | 0 1 | 00 01 11 10? (| for clarity only)

    If anything it would be [null] the first item in the list being: (Integer)null, but I guess it was just coerced to 0


  • 0

    Fixed the typo, thanks.

    with numbers would you really write 0 | 0 1 | 00 01 11 10 or just | 0 1 | 00 01 11 10?

    I wouldn't write the first one, as it's an inconsistent mix of fixed-length and non-fixed-length representation. The second one at least is consistent, but I don't like it, either. Really I'd either write "" | "0" "1" | "00" "01" "11" "10" or 0 | 0 1 | 0 1 3 2 (or 0 | 0 1 | 0 1 11 10 if I have a good reason to write in binary).

    What's your point with that, though? And why would it be null?


  • 0

    I don't know why I didn't realize this earlier, but... the problem statement says:

    Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

    So [] can't be the answer, as it doesn't begin with 0.


  • 0
    T

    Oh, that's right :) They could've just said positive n. There isn't much point is 0-length code. Following Wikipedia's motivation example: it would be a wall with no switches.

    I said null in the list because if you write down 0 you've written down one bit (which is "turned off"), which is not zero length; null, i.e. "nothing" better approximates a zero-length number IMO.

    If we notice the pattern that an n bit code has 2^n codepoints 2^0=1. I guess we both agree that single codepoint is the empty number, the question is how do we represent it. With that sentence the problem writer coerced that emptyness to 0.

    0 can be confusing...


  • 0

    I guess we both agree that single codepoint is the empty number

    No, I disagree. It's the empty code. And it represents the number zero.

    It's odd that you have no problem with "too many" zeros (leading zeros) but can't accept "too few" zeros. If you can accept "00000" to represent 0, why can't you accept "" to represent 0 as well? What's your reason to accept "00000" for 0? How do you evaluate "00000" to 0? I suspect that if you're consistent and evaluate "" the same way, you'll get 0.

    "nothing" better approximates a zero-length number IMO

    Numbers don't have lengths. Only representations of numbers do.


  • 0

    Btw, one more reason to like Python: It agrees that 0 needs only zero bits :-)

    >>> (0).bit_length()
    0
    

  • 0
    T

    No, I disagree. It's the empty code. And it represents the number zero.

    Yep, that's what I meant, sorry, bad choice of words there.

    Numbers don't have lengths. Only representations of numbers do.

    Hmm, that sound right. And I guess this is where 0-left-padded numbers come in as well. My first and mostly only exposure to binary was when I was learning Architecture 101 at uni, which was the only course incorporating "bit-twiddling, numeral systems and assembly". As you know CPUs always have limited space for numbers and it was easier to understand 7(dec) being 00000111(bin) on an 8-bit architecture, less surprises if that's your mental model (also notice that you can't pad decimals consistently this way). I always write decimal numbers without padding (like everyday people) and non-decimals are usually padded (in IT, just think about #0000FF representing blue in CSS). It's inconsistent, but that's how it stuck. Thanks for making me notice the difference between number and representing a number.

    "nothing" better approximates a zero-length number IMO

    Based on the above you should see that in my mind on a 0-bit architecture there wouldn't be space to store even a 0.

    If you can accept "000", "00" to represent 0, why can't you accept ""

    I guess it's too exceptional there, you can easily say "0001" = "001" = "01" = "1" = 1 (for anything > 0 there always remains something (2^31-2 times on 32-bits), but for 0 it's nothing (1 times, the exception).

    I hope you don't mind this quarrel about nothing (pun intended: 0) It's nice to have someone to discuss these things with!


  • 0

    in my mind on a 0-bit architecture there wouldn't be space to store even a 0

    Only because you make an exception for it, an extra rule that a representation can't be empty. I think it needs zero bits, and a 0-bit architecture has enough room for that :-)

    Thanks for making me notice the difference between number and representing a number.

    Haha, nice, that's actually one of my goals in life. Make everybody aware that there's a difference. It seems most people are so used to decimal representation that they think the representations are the numbers. Well, usually it doesn't matter and of course I use decimal representation, too. But sometimes it does matter.

    A nice example is 0.(9) and 1 being the same. The two representations aren't the same, but of course I only use representations in order to communicate. I'm really talking about the sameness of the represented numbers, and the two numbers are the same. But for people who never distinguish between representations and the represented numbers, I think this is a major reason why they have trouble with this example.

    I hope you don't mind this quarrel about nothing

    Not at all :-). I have btw noticed you quite a lot lately and enjoy and agree with many of your posts here.


  • 0
    T

    I really do think you would enjoy this Numberphile video about numbers a lot, or this one about 0 if you're more into math.


  • 0

    I think I've watched the first one before but I just watched it again and did enjoy it. At least until the end, when he says stuff like "I don't think [pi] is anything other than that endless sequence". Sequence? What sequence? Maybe "3.14159..."? That's not pi, that's a representation of pi. Grrr :-)

    I did watch the second one before, but might watch it again later as well. Anyway, thanks.


Log in to reply
 

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