LeetCode 2396. Strictly Palindromic Number

LeetCode Notes [43]

Problem

Strictly Palindromic Number - LeetCode

Approach 1: Convert to base b and check is palindromic or not

class Solution {
    fun isStrictlyPalindromic(n: Int): Boolean {
        for (i in 2..n - 2) {
            if (!isPalindromic(base(n, i))) return false
        }
        return true
    }

    private fun base(n: Int, base: Int): String {
        var result = ""
        var num = n
        while (num > 0) {
            result = "${num % base}$result"
            num /= base
        }
        return result
    }

    private fun isPalindromic(s: String): Boolean {
        val charArray = s.toCharArray()
        for (i in 0..charArray.size / 2 + 1) {
            if (charArray[i] != charArray[charArray.size - 1 - i])
                return false
        }
        return true
    }
}

Complexity Analysis

• Time Complexity: O(nlgn)
• Space Complexity: O(lgn)

Approach 2: Observation

For every base n — 2

• n = 4 -> 100 (false)
• n > 4 -> 21 (false, since n = (n-2) + 2)

We can’t find any n satisfy the constraint, so we can simply return false.

class Solution {
    fun isStrictlyPalindromic(n: Int): Boolean {
        return false
    }
}

Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)