Primes and Fast Exponentiation

Sieve of Eratosthenes (LeetCode 204)

Efficiently count prime numbers less than $n$.

public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!notPrime[i]) {
            count++;
            // Mark all multiples of i starting from i*i
            for (long j = (long)i * i; j < n; j += i)
                notPrime[(int)j] = true;
        }
    }
    return count;
}

Fast Exponentiation (LeetCode 50)

Compute $x^n$ in $O(\log n)$ time.

public double myPow(double x, int n) {
    long N = n;
    // Handle negative exponents
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }
    double result = 1.0;
    while (N > 0) {
        // If current bit is 1, multiply into result
        if ((N & 1) == 1) result *= x;
        // Square the base and shift to next bit
        x *= x;
        N >>= 1;
    }
    return result;
}

Ugly Number II (LeetCode 264)

Find the $n$-th ugly number (numbers whose prime factors are limited to 2, 3, and 5). Use three-way merge with pointers.

public int nthUglyNumber(int n) {
    int[] ugly = new int[n];
    ugly[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; i++) {
        int next2 = ugly[p2] * 2;
        int next3 = ugly[p3] * 3;
        int next5 = ugly[p5] * 5;
        
        int minNext = Math.min(next2, Math.min(next3, next5));
        ugly[i] = minNext;
        
        // Move all pointers that match the chosen minimum to avoid duplicates
        if (minNext == next2) p2++;
        if (minNext == next3) p3++;
        if (minNext == next5) p5++;
    }
    return ugly[n - 1];
}

Happy Number (LeetCode 202)

Determine if a number is "happy." Use Floyd's Cycle-Finding Algorithm (slow and fast pointers).

public boolean isHappy(int n) {
    int slow = n;
    int fast = getNext(n);
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast == 1;
}

private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

筋