Codility Lesson 9

9_CountNonDivisible.java

import java.util.HashMap;

class Solution {
    public int[] solution(int[] A) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> resmap = new HashMap<Integer, Integer>();
        int[] res = new int[A.length];
        
        for (int i=0; i<A.length; i++) {
            int count = 1;
            if (map.containsKey(A[i]))
                count += map.get(A[i]);
            map.put(A[i], count);
        }
        
        for (int N : map.keySet()) {
            int count = 0;
            int i = 1;
            while (i * i <= N) {
                if (N % i == 0) {
                    if (map.containsKey(i))
                        count += (int)map.get(i);
                    if (map.containsKey(N/i) && N/i != i)
                        count += (int)map.get(N/i);
                }
                i++;
            }
            resmap.put(N, A.length-count);
        }
        
        for (int j=0; j<A.length; j++)
            res[j] = resmap.get(A[j]);
        
        return res;
    }
}

9_CountSemiPrimes.java

class Solution {
    public int[] solution(int N, int[] P, int[] Q) {
        int[] res = new int[P.length];
        int[] sieve = new int[N+1];
        int[] p = new int[N+1];
        
        for (int i=2; i*i <= N; i++) {
            int k=i*i;
            while (k<=N) {
                if (sieve[k] >= 0) {
                    if (definePrime(k/i))
                        sieve[k] = 1;
                    else
                        sieve[k] = -1;
                }
                k += i;
            }
        }
        
        for (int i=1; i<N+1; i++) {
            if (sieve[i] > 0)
                p[i] = p[i-1]+1;
            else
                p[i] = p[i-1];
        }
        
        for (int i=0; i<P.length; i++)
            res[i] = p[Q[i]] - p[P[i]-1];
        
        return res;
    }
    
    private boolean definePrime(int n) {
        int i = 2;
        while (i*i<= n) {
            if (n % i == 0)
                return false;
            i++;
        }
        return true;
    }
}