Ref: link

204. Count Primes (Easy)

This problem is easy but we need to take care of run time. You may want to check all numbers whether are prime numbers which are less than n. Sure, we need to check all numbers less than n. But when we find a prime number, we can skip some numbers which can be divided by this prime number. We need an array to store whether the number i is a prime number. If number[i] is a prime number, we need to know number[i]*j, 1<=j && number[i]*j<n is not a prime number. We can use a for loop to skip these numbers to accelerate the algorithm.

Time complexity is O(n^2). Space complexity is O(n).

    class Solution {
        public int countPrimes(int n) {
            int ans = 0;
            int[]array = new int[n];
            for(int i = 2;i<n;i++){
                if(array[i]==1)continue;
                ans++;
                for(int j = 1;j*i<n;j++){
                    array[j*i]=1;
                }
            }
            return ans;
        }
    }

504. Base 7 (Easy)

For example, we can use 100 divided by 7 at first. We get 14 and remainder 2. And we use 14 divided by 7. We get 2 and remainder 0, so we get 202.

The time complexity depends on the value of input number. The space complexity is O(1). Here is the link.

    class Solution {
        public String convertToBase7(int num) {
            if(num<0)return "-"+convertToBase7(0-num);
            if(num<7)return String.valueOf(num);
            return convertToBase7(num/7)+ String.valueOf(num%7);
        }
    }

405. Convert a Number to Hexadecimal (Easy)

This problem is similar to the last problem. But we need to consider letters this time, so we can have an array or a string to store the integer value of letters from a to f. In each iteration, we deal with the most right 4 digits. We use num & 0xf to find the value of the most 4 digits. And then we move to right with 4 digits. Until the value of num is 0 or we have done 8 operations, we stop.

Time complexity is O(1). Space complexity is O(1). Here is the link.

    class Solution {
        public String toHex(int num) {
            String res = ""; String str= "0123456789abcdef";
            int cnt = 0;
            while (num != 0 && cnt++ < 8) {
                res = str.charAt(num & 0xf) + res;
                num >>= 4;
            }
            return res.length()==0 ? "0" : res;
        }
    }

168. Excel Sheet Column Title (Easy)

We need to delete 1 in each iteration because we start from 1, not 0.

Time complexity depends on the value of n. Space complexity is O(1). Here is the link.

    public String convertToTitle(int n) {
        if (n == 0) {
            return "";
        }
        n--;
        return convertToTitle(n / 26) + (char) (n % 26 + 'A');
    }

172. Factorial Trailing Zeroes (Easy)

We need to find how many 5 does value n contain. In order to get trailing zeroes, we need 5 and 2. If we can find a trailing 5, we can also find a trailing 2, like 15 and 12, 25 and 22.

Time complexity is O(n). Space complexity is O(1). Actually, we can use binary solution to reduce time complexity to O(logn). Here is the link.

    class Solution {
        public int trailingZeroes(int n) {
            int ans = 0;
            while(n>0){
                ans+=n/5;
                n/=5;
            }
            return ans;
        }
    }