Java O(n) Time complexity and O(1) Space complexity with explanation.


  • 0
    J

    consider x = 1221

    To check of palindrome condition we need to compare the units place(tail) of the number with the max place value (head) (1000th place for this example).

    So, we first calculate the number of places in the number and store it in ‘places’ variable.

    Then we loop over the number to iteratively fetch the head and tail digits for comparison.
    After each loop, we remove the head and tail digits of the number.

    To do this,
    1.we get the remainder of current number when divided by the max place value

    1. Then divide the remainder by 10 to remove the units place digits.
    2. Since we removed two digits the places variable has to be divided by 100.

    1221 —> 1221%1000 —>221->221/10 —> 22.

    Java O(n) implementation :-

    	public boolean isPalindrome(int x) {
    		if (x < 0) return false;
    		
    		int places = 1;
    		while (x / places >= 10) {
    			places = places * 10;
    		}
    		while (x != 0) {
    			int tail = x % 10;
    			int head = x/places;
    			if (tail != head) {
    				return false;
    			}
    			x = (x % places) / 10;
    			places = places /100;
    		}
    		return true;
    	}
    
    

Log in to reply
 

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