650. 2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/description/
When n != 0, there the results is the sum of its prime factors.
    int minSteps(int n) {
        if(n == 1) return 0;
        int res = 0;
        vector<int> prime(n+1, 0);
        for(int i=2; i<prime.size(); i++) prime[i] = i;
        for(int i=2; i<prime.size(); i++) {
            int p = prime[i];
            if(p) {
                for(int j=2*p; j<prime.size(); j+=p) prime[j] = 0;
                while(n%p == 0) {
                   res += p;
                    n /= p;
                }
            }
        }
        return res;
    }

498. Diagonal Traverse

https://leetcode.com/problems/diagonal-traverse/description/
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if(matrix.size() == 0) return {};
        int M = matrix.size();
        int N = matrix[0].size();
        int K = M+N-2;
        vector<int> res;
        for(int k=0; k<=K; k++) {
            int i=0, j=0, d;
            if(k%2 == 0) {
                i = k<M? k:M-1;
                j = k-i;
                d = -1;
            }
            else {
                j = k<N? k:N-1;
                i = k-j;
                d = 1;
            }
            while(i>=0 && i<M && j>=0 && j<N) {
                res.push_back(matrix[i][j]);
                i += d;
                j -= d;
            }
        }
        return res;
    }

357. Count Numbers with Unique Digits

https://leetcode.com/problems/count-numbers-with-unique-digits/description/
n     digits:   9*8*7*...
n-1  digits:       9*8*...
1     digits nonzero:      9
1     digits zero:            1
    int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        if(n>10) return 0;
        int res = 1;
        for(int i=1; i<n; i++) {
            int t = 1;
            for(int j=1; j<=i; j++) {
                t *= (10-j);
            }
            res += t;
        }
        res *= 9;
        return res+1;
    }

343. Integer Break

https://leetcode.com/problems/integer-break/description/
    int integerBreak(int n) {
        if(n == 2)
            return 1;
        else if(n == 3)
            return 2;
        else if(n%3 == 0)
            return (int) pow(3, n/3);
        else if(n%3 == 1)
            return 2 * 2 * (int) pow(3, (n - 4) / 3);
        else
            return 2 * (int) pow(3, n/3);
    }

592. Fraction Addition and Subtraction

https://leetcode.com/problems/fraction-addition-and-subtraction/description/
Solution. gcd(a,b) find the greatest common divisor. Then the irreducible fraction can be found.
    string fractionAddition(string exp) {
        string delim = "+-";
        if(exp[0]>='0' && exp[0]<='9') exp = "+" + exp;
        size_t pos = 0, start = 0, dv;
        string res = "", b;
        int n = 0, d = 1, nb, db, nn;
        while(start != string::npos){
            pos = exp.find_first_of(delim, start+1);
            b = exp.substr(start, pos - start);
            dv = b.find_first_of("/", 0);
            nb = stoi(b.substr(0, dv));
            db = stoi(b.substr(dv+1));
           
            n = n*db + d*nb;
            d = d*db;
            int g = gcd(abs(n), d);
            n /= g;
            d /= g;

            start = pos;
        }
        return res + to_string(n) + "/" + to_string(d);
    }
    int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a%b);
    }

553. Optimal Division

https://leetcode.com/problems/optimal-division/description/
    string optimalDivision(vector<int>& nums) {
        if(nums.size()==0) return "";
        if(nums.size()==1) return to_string(nums[0]);
        string res = to_string(nums[0]);
        if(nums.size()==2) return res+"/"+to_string(nums[1]);
        res += "/(";
        for(int i=1; i<nums.size(); i++) {
            res += to_string(nums[i]) + "/";
        }
        res[res.size()-1] = ')';
        return res;
    }

537. Complex Number Multiplication

https://leetcode.com/problems/complex-number-multiplication/description/
Solution 1.stringstream
    string complexNumberMultiply(string a, string b) {
        int ar, ai, br, bi;
        char buff;
        stringstream ssa(a), ssb(b), res;
        ssa >> ar >> buff >> ai >> buff;
        ssb >> br >> buff >> bi >> buff;
        res << ar*br - ai*bi << "+" << ar*bi + br*ai << "i";
        return res.str();
    }
Solution 2. strtok
    string complexNumberMultiply(string a, string b) {
        string ars = strtok((char*)a.c_str(), "+i");
        string ais = strtok(NULL, "+i");
        string brs = strtok((char*)b.c_str(), "+i");
        string bis = strtok(NULL, "+i");
        long ar = stol(ars);
        long ai = stol(ais);
        long br = stol(brs);
        long bi = stol(bis);
        long re = ar*br - ai*bi;
        long im = ar*bi + ai*br;
     
        return to_string(re)+"+"+to_string(im)+"i";
    }

7. Reverse Integer

https://leetcode.com/problems/reverse-integer/description/
    int reverse(int x) {
        if(x == INT_MIN) return 0;
        if(x < 0) return -reverse(-x);
        int res = 0;
        while(x) {
            int r = x%10;
            if(res > INT_MAX/10) return 0;
            res = res * 10 + r;
            x /= 10;
        }
        return res;
    }

168. Excel Sheet Column Title

https://leetcode.com/problems/excel-sheet-column-title/description/

    string convertToTitle(int n) {
        string s = "";
        while(n) {
            n--;
            s = char('A' + n%26) + s;
            n /= 26;
        }
        return s;
    }

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;
    }

69. Sqrt(x)

https://leetcode.com/problems/sqrtx/description/
Solution 1.
    int mySqrt(int x) {
        if(x == 0) return 0;
        int n = 0;
        for(int m = 1<<30; m!=0; m>>=1){
            int r = n|m;
            while(r>x/r) {
                m >>= 1;
                r = n|m;
            }
            n |= m;
        }
        return n;
    }
Solution 2
    int mySqrt(int x) {
        if(x == 0) return 0;
        double y = log10(x)/2.;
        return (int) pow(10.,y);
    }

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;
    }

633. Sum of Square Numbers

https://leetcode.com/problems/sum-of-square-numbers/description/
    bool judgeSquareSum(int c) {
        int a = sqrt((double) c / 2.0);
        int b = a;
        int c2 = sqrt(c);
        while(a>=0 && b<=c2) {
            int s = a*a + b*b;
            if(s<c) b++;
            else if(s>c) a--;
            else return true;
        }
        return false;
    }

67. Add Binary

https://leetcode.com/problems/add-binary/description/

    string addBinary(string a, string b) {
        if(a.size()<b.size()) return addBinary(b, a);
        int c = 0;
        int j = b.size()-1, i = a.size()-1;
        for(;i>=0 && (c||j>=0); i--,j--,c/=2) {
            c += a[i] - '0' + (j>=0? b[j] - '0':0);
            a[i] = c%2 + '0';
        }
        return (c? "1":"") + a;
    }

507. Perfect Number

https://leetcode.com/problems/perfect-number/description/

if(num == 1) return false;
        int s = 1, N = sqrt(num);
        for(int i=2; i<=N;i++) {
            if(num%i == 0) s += i + num/i;
        }
        if(s == num) return true;
        return false;
    }

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;
    }

643. Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/
Solution 1. Sliding window.
double findMaxAverage(vector<int>& nums, int k) {
        int start = 0, end = 0, sum = 0, res = INT_MIN;
        while(end < nums.size()) {
            sum += nums[end];
            if(end - start + 1 == k) {
                res = max(sum, res);
                sum -= nums[start++];
            }
            end++;
        }
        return (double)res/(double)k;
    }
or,
    double findMaxAverage(vector<int>& nums, int k) {
        int mx = 0, s = 0, i = 0, j = 0;
        for(j=0; j<k; j++) s += nums[j];
        mx = s;
        while(j < nums.size()) {
            s = s - nums[i++] + nums[j++];
            mx = max(mx, s);
        }
        return double(mx)/k;
    }

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;
    }

342. Power of Four

https://leetcode.com/problems/power-of-four/description/
Solution 1. Shift and compare the last 2 bits on the left.
    bool isPowerOfFour(int num) {
        if(num<=0) return false;    
        while(num){
            if(num&3) {
                if(num == 1) return true;
                return false;
            }
            num >>= 2;
        }
        return true;
    }
Solution 2. It can be fit in one line. A number is power of 4 only if num>4 and only 1 nonzero bit and the nonzero bit is at 1, or 3, or 5 ...
    bool isPowerOfFour(int num) {
        return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num);
    }

66. Plus One

https://leetcode.com/problems/plus-one/description/
    vector<int> plusOne(vector<int>& digits) {
        int c = 1, t;
        for(int i=digits.size()-1; i>=0 && c; i--) {
            digits[i] += c;
            c = digits[i]/10;
            digits[i] %= 10;
        }
        if(c) digits.insert(digits.begin(), 1);
        return digits;
    }