Nano InkNano Ink

Palindrome Number (LeetCode 9)

9. Palindrome Number

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:
Input: x = 121
Output: true

Example 2:
Input: x = -121
Output: false

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        int rev = 0, temp = x;
        while (temp != 0) {
            rev = rev * 10 + temp % 10;
            temp /= 10;
        }
        return rev == x;
    }
}
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        rev, temp = 0, x
        while temp != 0:
            rev = rev * 10 + temp % 10
            temp //= 10
        return rev == x
Type Value
Time O(log(x))
Space O(1)
  • Dry run (x=121): rev=1→12→121, temp→12→1→0 → rev==x → true

Happy Number (LeetCode 202)

202. Happy Number

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.

Example 1:
Input: n = 19
Output: true

Example 2:
Input: n = 2
Output: false

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    private int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}
class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num):
            total_sum = 0
            while num > 0:
                digit = num % 10
                total_sum += digit ** 2
                num //= 10
            return total_sum
            
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)
        return n == 1
Type Value
Time O(log(n))
Space O(log(n))
  • Approach: Use a HashSet to detect cycles. Keep summing digits until 1 or cycle detected.
  • Dry run (n=19): 19 → 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1 → return true

Add Digits (leetcode 258)

258. Add Digits

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:
Input: num = 38
Output: 2
Explanation: The process is 38 --> 3 + 8 --> 11 --> 1 + 1 --> 2. Since 2 has only one digit, return it.

Example 2:
Input: num = 0
Output: 0

class Solution {
    public int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
}
class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        return (num - 1) % 9 + 1
Type Value
Time O(1)
Space O(1)
  • Approach: Use the property of digital root. (num - 1) % 9 + 1 gives the digital root of the number.
  • Dry run (num=38): (38-1) % 9 + 1 = 37 % 9 + 1 = 1 + 1 = 2 → Answer is 2.

Ugly Number (leetcode 263)

263. Ugly Number

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return true if n is an ugly number.

Example 1:
Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:
Input: n = 14
Output: false
Explanation: 14 includes the prime factor 7.

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        for (int i = 2; i <= 5; i++) {
            while (n % i == 0) n /= i;
        }
        return n == 1;
    }
}
class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        for i in [2, 3, 5]:
            while n % i == 0:
                n //= i
        return n == 1
Type Value
Time O(log(n))
Space O(1)
  • Approach: Keep dividing by 2, 3, and 5. If the result is 1, it's an ugly number.
  • Dry run (n=14): 14/2=7. 7 is not divisible by 2, 3, or 5. n=7 ≠ 1 → return false.

Reverse Integer (LeetCode 7)

7. Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

class Solution {

    public int reverse(int x) {
        int rev = 0;
        while(x != 0){
            int digit = x % 10;
            x = x / 10;
            if(rev > Integer.MAX_VALUE/10 || rev < Integer.MIN_VALUE/10){
                return 0;
            }
            rev = rev * 10 + digit;
        }
        return rev;
    }
}
class Solution:
    def reverse(self, x: int) -> int:
        sign = -1 if x < 0 else 1
        x *= sign
        rev = 0
        while x != 0:
            digit = x % 10
            rev = rev * 10 + digit
            x //= 10
            
        rev *= sign
        if rev < -2**31 or rev > 2**31 - 1:
            return 0
        return rev
Type Value
Time O(log(x))
Space O(1)
  • Approach: Repeatedly extract the last digit with % 10 and build the reversed number. Check for overflow before appending the digit.
  • Dry run (x = 123):
    • digit=3, rev=3, x=12
    • digit=2, rev=32, x=1
    • digit=1, rev=321, x=0
    • Returns 321.

Prime Sum (GeeksforGeeks)

Prime Sum

Example 1:

Input: n = 10
Output: 17
Explanation: The prime numbers less than or equal to 10 are 2, 3, 5, and 7. Their sum is 2 + 3 + 5 + 7 = 17.

class Solution {
    public int prime_Sum(int n) {
        if (n < 2) return 0;

        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j +=i) {
                    isPrime[j] = false;
                }
            }
        }

        int sum = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                sum += i;
            }
        }

        return sum;
    
    }
}
class Solution:
    def prime_Sum(self, n: int) -> int:
        if n < 2:
            return 0
            
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        
        i = 2
        while i * i <= n:
            if is_prime[i]:
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
            i += 1
            
        return sum(i for i in range(2, n + 1) if is_prime[i])
Type Value
Time O(n log log n)
Space O(n)
  • Approach: Use Sieve of Eratosthenes to find all primes up to n and sum them.
  • Dry run (n=10):
    • isPrime = [T,T,T,T,T,T,T,T,T,T,T]
    • i=2: isPrime[2]=T → isPrime[4]=F, isPrime[6]=F, isPrime[8]=F, isPrime[10]=F
    • i=3: isPrime[3]=T → isPrime[9]=F
    • i=4: isPrime[4]=F → skip
    • i=5: isPrime[5]=T → isPrime[10]=F
    • i=6: isPrime[6]=F → skip
    • i=7: isPrime[7]=T → isPrime[14]=F
    • i=8: isPrime[8]=F → skip
    • i=9: isPrime[9]=F → skip
    • i=10: isPrime[10]=F → skip
    • sum = 2+3+5+7 = 17