Does converting the integer to a String mean using extra space?


  • 0
    T

    My understanding is that converting the integer to a string uses O(1) space.

    Not sure if this is a correct solution for this problem.


  • 2
    M

    In the spoilers:

    If you are thinking of converting the integer to string, note the restriction of using extra space.
    

    So yes, that counts as using extra space. In fact, it isn't even O(1) space. As the ints are decimal based, it will take 1 char for each place, or log10(n) spaces. Therefore, converting to a string takes O(log n) space. You are on the right track, but see if you can't access the first and last places without using strings. % and / should help you there.


  • 0
    D

    There would be at most 10 chars only. so your log10(n) spaces is actually smaller than 11. It is O(1)space.


  • 0
    M

    There are languages where unsigned ints are defined as 64 bits, so can range to 2^64-1, meaning it is up to 20 numbers long in those languages. There is nothing algorithmically defining an int to be 32 bits, or 10 chars at most. Therefore, the length of the int is the only measure for how long the algorithm is, with the simplest conversion being 1 place to 1 char, or log10(n) chars at the maximum. Regardless of how small a given solution for log10(n) is, the growth is logarithmic, and so the space is O(log n).

    The idea of being O(1) because it takes less than 11 spaces follows the same reasoning that a sorted 3-int array could find a give element's index using binary search in 2 steps at most, so the search will take O(1) time. The size of the array, in practice, is limited by the size of the memory in the computer, so has a hard limit, similarly to a defined length for ints. However, if you expand the list beyond that by adding more memory, the number of steps will increase according to O(log n), not at O(1), even though the algorithm didn't change at all.


  • 2
    L
    public class Solution {
    public boolean isPalindrome(int x) {
        int y=0;
        int t=x;
        while(t>0){
            y=y*10+t%10;
            t=t/10;
        }
        if(x==y) return true;
        else return false;
    }
    

    }


  • 0
    L

    In your answer, Y might overflow.


  • 0
    Z
        public boolean isPalindrome(int x) {
            int temResult = 0;
            int temX = x;
            while (temX > 0) {
                temResult = temResult * 10 + temX % 10;
                temX = temX / 10;
            }
            return x == temResult;
        }
    

    the return can be more simpler.


Log in to reply
 

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