You wanted solution with no extra space? You got it!


  • 6

    But it's terribly silly. And the compiler might want to optimize it by using temporary variables, and that's a kind of extra space I'm not responsible for.

    public boolean isPalindrome(int x) {
        if (x < 0 || x > 0 && x % 10 == 0) {
            return false;
        } else {
            return x / 10 == 0 || x / 10 == x % 10 || x / 100 > 0 && x / 100 == x % 10 // 1-3 digits
                   || x / 100 > 0 && x / 100 ==       x % 10 * 10   + x % 100 / 10 // 4 digits
                   || x / 1000 > 0 && x / 1000 ==     x % 10 * 10   + x % 100 / 10 // 5 digits
                   || x / 1000 > 0 && x / 1000 ==     x % 10 * 100  + x % 100 / 10 * 10  + x % 1000 / 100 // 6 digits
                   || x / 10000 > 0 && x / 10000 ==   x % 10 * 100  + x % 100 / 10 * 10  + x % 1000 / 100 // 7 digits
                   || x / 10000 > 0 && x / 10000 ==   x % 10 * 1000 + x % 100 / 10 * 100 + x % 1000 / 100 * 10
                                                      + x % 10000 / 1000 // 8 digits
                   || x / 100000 > 0 && x / 100000 == x % 10 * 1000 + x % 100 / 10 * 100 + x % 1000 / 100 * 10
                                                      + x % 10000 / 1000 // 9 digits
                   || x / 100000 > 0 && x / 100000 == x % 10 * 10000 + x % 100 / 10 * 1000 + x % 1000 / 100 * 100
                                                      + x % 10000 / 1000 * 10 + x % 100000 / 10000; // 10 digits
        }
    }

  • 0

    You're right, I got it :-P (and WeiliZhang first, as far as I know).

    Yours is interesting as well, though. And a bit shorter, I think. I'd just remove the "else", no need since the "if" returns. Or you could combine the two returns into just one, which I think would also be neat.


  • 0

    I wonder if return x == 0 || x == 1 || x == 2 || ... || x == 2147447412; would also work. That would be even purer. And it's only 121474 values, and without the spaces only 1.6 MB :-)


  • 0

    I usually leave the else part there for clarity, if it's not very long. But it's a matter of personal preference. I haven't thought of combining expressions, though—a very nice idea. But you raise an interesting point here: if we consider space needed for constants (and for the opcodes, for that matter!), then there is no such thing as “no extra space” solutions for any kind of problems.


  • 0

    Yeah, it's not long, but it causes an indentation level that I dislike.

    Haha, constants/code taking extra space wasn't even my point, I was just joking about such a dumb huge program :-). And I'd actually say it isn't "extra". Since we have to have some code and are required to not use extra space, code can't be considered extra space. And I'd say constants are just part of the code.

    Fun fact: Complaining about this and requesting a fix was one of the earliest things I did at LeetCode :-). To quote myself: "even the final solution presented by the article (http://articles.leetcode.com/2012/01/palindrome-number.html) does use three (!) extra ints."


  • 0

    Surely it was a joke, but it's something worth considering anyway (e. g. huge switch statements vs auxiliary arrays). By the way, I don't think Java will allow the dumbest solution because it has a “code is too long” compilation error. I got it sometimes when copy-pasting test cases (huge arrays) into my code.

    Yeah, three extra ints are not extra space, and 10 additional bytes is? Figures. To be fair, in Java 10 bytes array is not 10 bytes because of the object overhead, but that's language-specific.


  • 0
    N

    I fell for that clickbait, lol!
    Good one.


Log in to reply
 

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