719. Find K-th Smallest Pair Distance

    int smallestDistancePair(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int lo = 0, hi = nums.back() - nums.front(), mid;
        while(lo<hi) {
            mid = (lo + hi)/2;
            // count number of distances that is <= mid;
            int cnt = countDist(nums, mid);
            if(cnt >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    int countDist(vector<int>& n, int dist) {
        int i = 0, j = 0, cnt = 0;
        for(; i < n.size(); i++) {
            while(j<n.size() && n[j] - n[i] <= dist) j++;
            cnt += j - i -1;
        }
        return cnt;
    }

712. Minimum ASCII Delete Sum for Two Strings

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
Solution 1.
int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m+1, vector<int> (n+1, 0));
        dp[0][0] = 0;
        for(int i=1; i<m+1; i++) dp[i][0] = dp[i-1][0] + s1[i-1];
        for(int j=1; j<n+1; j++) dp[0][j] = dp[0][j-1] + s2[j-1];
        for(int i=1; i<m+1; i++) {
            for(int j=1; j<n+1; j++) {
                if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
                else {
                    dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
                }
            }
        }
        return dp[m][n];
    }

477. Total Hamming Distance

https://leetcode.com/problems/total-hamming-distance/description/
    int totalHammingDistance(vector<int>& nums) {
        if(nums.size()<2) return 0;
        int N = nums.size();
        int res = 0, w=1;
        for(int i=0; i<32; i++) {
            int n1 = 0;
            for(int j=0; j<N; j++) {
                n1 += (nums[j]&w)!=0;
            }
            res += n1*(N-n1);
            w <<= 1;
        }
        return res;
    }

526. Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement/description/

    void count(int N, vector<bool>& fil, int& res) {
        if(N==0) {res++; return;}
       
        for(int i=fil.size()-1; i>=0; i--) {
            if(!fil[i] && (N%(i+1)==0 || (i+1)%N==0)){
                fil[i] = true;
                count(N-1, fil, res);
                fil[i] = false;
            }
        }
    }
    int countArrangement(int N) {
        int res = 0;
        vector<bool> fil(N, false);
        count(N, fil, res);
        return res;
    }

189. Rotate Array

https://leetcode.com/problems/rotate-array/description/
Solution 1. O(1) space, 3 reversions
    void rotate(vector<int>& nums, int k) {
        int N = nums.size();
        if(N ==0 || k%N ==0) return;
        k = k%N;
        reverse(begin(nums), begin(nums)+N-k);
        reverse(begin(nums)+N-k, end(nums));
        reverse(begin(nums), end(nums));
    }
Solution 2. O(1) space, keep rotating one by one until total number of rotating = nums.size()
    void rotate1(vector<int>& nums, int k) {
        int N = nums.size();
        if(N ==0 || k%N ==0) return;
        k = k%N;
        int cnt = 0, iStart = 0, iCurrt = 0, numRot = nums[0], tmp;
        while(cnt<N) {
            do{
                iCurrt = (iCurrt + k)%N;
                tmp = nums[iCurrt];
                nums[iCurrt] = numRot;
                numRot = tmp;
                cnt++;
            }while(iStart != iCurrt);
           
            iStart++;
            iCurrt = iStart;
            numRot = nums[iCurrt];
        }

    }
Solution 3.
    void rotate(vector<int>& nums, int k) {
        int N = nums.size();
        k = k%N;
        if(k == 0) return;
        vector<int> nk(k);
        for(int i=0; i<k; i++) nk[i] = nums[N-k+i];
     
        for(int i=N-k-1; i>=0; i--) {
            nums[i+k] = nums[i];
        }

        for(int i=0; i<k; i++) nums[i] = nk[i];
    }

204. Count Primes

https://leetcode.com/problems/count-primes/description/
Solution 1. Use Sieve of Eratosthenes (13 ms)
    int countPrimes(int n) {
        if(n<=2) return 0;
        bool s[n] = {false}; // faster than vector<bool> s(n,false);
        int np = 1;
        for(int i=3; i<n; i+=2) {
            if(!s[i]) {
                np++;
                if(i>n/i) continue;
                for(int j=i*i, step=i<<1; j<n; j+=step) {
                    //set step = 2*i to ignore even numbers
                    s[j] = true;
                }
            }
        }
        return np;
    }

400. Nth Digit

https://leetcode.com/problems/nth-digit/description/
    int findNthDigit(int n) {
        vector<int> sd(9,0);
        int d;
        for(d=1; d<9; d++) {
            // d is the length (digits of a single number) of a number
            // sd is the total digits for length from 1 to d
            sd[d] = d*pow(10, d) - (pow(10,d)-1)/9;
            if(sd[d]>=n) break;
        }
        // the length of number prior to the current length
        int d1 = d-1;
        // total digits for length d is n - total digits for length from 1 to d-1
        n -= sd[d1];
        // the number is i-th of numbers with length d
        int i = (n-1)/d;
        // the first number of length d is
        int a = pow(10, d1);
        // what is the number
        a += i;
        // the digit is the i-th digit of the number a
        i = n - i*d;
        // return the digit
        return (a/(int)(pow(10,d-i))) % 10;
    }

172. Factorial Trailing Zeroes

https://leetcode.com/problems/factorial-trailing-zeroes/description/
Solution. The number of trailing 0 of n! equals the total number of factor 5 in 1, 2, ... , n. 
Each step, n/5 is the number of integers that have at least one factor of 5 in 1,2,...,n.
    int trailingZeroes(int n) {
        if(n == 0) return 0;
        int nz = 0;
        while(n) {
            nz += n/5;
            n /= 5;
        }
        return nz;
    }

441. Arranging Coins

https://leetcode.com/problems/arranging-coins/description/
Solution 1. Subtract the s-th row from n each time.
    int arrangeCoins(int n) {
        int s = 0;
        while(n>s) {
            s++;
            n -= s;
        }
        return s;
    }
Solution 2. A full staircase with s rows and n coins has s(s+1) = 2*n.
Thus s = (-1 + sqrt(1+8*n)) / 2 = (-0.25 + sqrt(2*n + 0.25).
    int arrangeCoins(int n) {
        return floor(-0.5+sqrt((double)2*n+0.25));
    }

367. Valid Perfect Square

https://leetcode.com/problems/valid-perfect-square/description/
Solution 1. For 32 bit integer input num, sqrt(num) < pow(2,16). Let n=0, Start from 15th bit, n = n + pow(2,15). If num < n*n, decreasing n to pow(2,14), pow(2,13), ... until num > n*n, say n = pow(2,i). Then start again from i-1 bit.
     bool isPerfectSquare(int num) {
        vector<int> sq;
        int n = 0;
        for(int i=15; i>=0; i--){
            while(pow(n+(1<<i),2) > num && i>=0) i--;
            n += (1<<i);
            if(pow(n,2) == num) return true;
        }
        return false;
    }
Solution 2. 1 + 3 + 5 + ... + (2n-1) = n*n
     bool isPerfectSquare(int num) {
        int i = 1;
        while (num > 0) {
            num -= i;
            i += 2;
        }
        return num == 0;
    }