Palindrome Permutation

★★☆☆☆

Given a string, determine if a permutation of the string could form a palindrome.

For example, "code" -> False, "aab" -> True, "carerac" -> True.

Note: really good implementation and thoughts

public boolean canPermutePalindrome(String s) {
    Set<Character> cset = new HashSet<>();
    for (int i = 0; i < s.length(); ++i) {
        char c = s.charAt(i);
        if (cset.contains(c)) cset.remove(c);
        else cset.add(c);
    }
    return cset.size() == 1 || cset.size() == 0;
}

Count Primes

★★☆☆☆

Count the number of prime numbers less than a non-negative number, n.

Notes:

• Let's write down all of 12's factors:

 2 × 6 = 12
 3 × 4 = 12
 4 × 3 = 12
 6 × 2 = 12

As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.

• Sieve of Eratosthenes
• in the seconde loop, if you use (int m = 2; m < n/i; ++m) instead, there might be some cast issue to get a bug..., try n == 13

public int countPrimes(int n) {
    if (n <= 2) return 0;
    boolean[] notPrime = new boolean[n];
    int count = 0;
    for (int i = 2; i < n; ++i) {
        if (!notPrime[i]) {
            count++;
            for (int m = 2; i*m < n; ++m) notPrime[i*m] = true;
        }
    }
    return count;
}