Java using no additional space, but not efficient, any suggestion?


  • 0
    P

    Since I don't want to use any additional space, I did not convert it to a string.
    First compute how many digits are there using log10(x);
    then compare the most significant digit and the least significant digit, move one digit inside, and repeat.
    time complex should be O(n), but actual program performs cost 1606ms..

        public boolean isPalindrome(int x) {
    	double num = Math.abs((double) x);
    	System.out.println(num);
        int length = (int) Math.log10(num) + 1;
        System.out.println(length);
        for (int i = 1; i < length / 2 + 1; i++){
        	double m = Math.floor((num%(Math.pow(10, i)))/Math.pow(10, i-1));
        	double n = Math.floor((num%(Math.pow(10, length - i + 1)))/Math.pow(10, length - i));
        	if (m != n){
        		return false;
        	}	
        }
        return true;
    }

  • 0
    H

    i like the idea of using log10, but seems calling such a func would be inefficient.


  • 0
    P

    The log will only be calculated once


  • 0
    S

    By using some /, % operations, we can fetch the number in each position. Mine runs for 371ms.

    public boolean isPalindrome(int x) {
      if (x < 0)
          return false;
      if (x < 10)
          return true;
      int copy = x;
      int tens = 1;
      while (copy / 10 != 0) {
          copy = copy / 10;
          tens = tens * 10;	
      }  
      while (x > 0 && tens > 0) {
          int h = x / tens;
          h = h % 10;
          int l = x % 10;
          if (h != l)
    	    return false;
          x = x / 10;
          tens = tens / 100;
      }  
      return true; 
    }

Log in to reply
 

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