General
It’s always tricky to solve a math problem especially something difficult which might require sophisticated understanding of mathematics including permutation and combination, probability theory and even digital logic design and the like. However, using math can always solve problems in a very efficient and clean way, so do not hesitate to dive into this. We will go through this topic in a practical way, checking examples as many as possible.
Examples
All techniques are in the examples shown below which all in C++, enjoy the journey.
Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:
 Fill any of the jugs completely with water.
 Empty any of the jugs.
 Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.12345678910111213141516class Solution {private:int gcd(int a, int b) {return b? gcd(b, a%b):a;}public:bool canMeasureWater(int x, int y, int z) {//constraint 3if(x+y < z) return false;//in case of zeroif(x==z  y==z) return true;//Bezout's identity  xa+yb=d//(1*3+2*5=4, negative means pouring out, positive means filling up)return z%gcd(x, y) == 0;}};
Sqrt implementation
Binary search method


Newton method


Count Numbers with Unique Digits
Given a nonnegative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99]).


Power of Three
Quite simple problem but there are ways of doing this. (recursive, iterative, mapchecking and math, pow and log are often used)


Super Ugly Number
Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.


Integer to English Words
Convert a nonnegative integer to its english words representation. Given input is guaranteed to be less than 231  1.
For example,
123 > “One Hundred Twenty Three”
12345 > “Twelve Thousand Three Hundred Forty Five”
1234567 > “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”


Add Digits
Given a nonnegative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up: Could you do it without any loop/recursion in O(1) runtime?
Basic


Trick


Number of Digit One
Given an integer n, count the total number of digit 1 appearing in all nonnegative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.


Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign , nonnegative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
“1 + 1” = 2
“ 21 + 2 “ = 3
“(1+(4+5+2)3)+(6+8)” = 23
Iterative method


Recursive method


Rectangle Area
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Rectangle Area
Assume that the total area is never beyond the maximum possible value of int.


Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.


Happy Number
Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Basic


Trick


Count Primes
Count the number of prime numbers less than a nonnegative number, n.
Basic method


Optimized method


Excel Sheet Column Title
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example: 1 > A 2 > B 3 > C … 26 > Z 27 > AA 28 > AB
Iterative


Recursive


Fraction to Recurring Decimal
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.
Imitating the division process is the key.


String to Integer (atoi)
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.


Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Basic


Mapping


Roman to Integer


Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT. Similar problem  sqrt(x).
Bit manipulation actually


Trick using div, still log can also do the same


Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = “11”
b = “1”
Return “100”.


Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
Basic


Trick


Valid Number
Validate if a given string is numeric.
Some examples:
“0” => true
“ 0.1 “ => true
“abc” => false
“1 a” => false
“2e10” => true


Use strtof
to handle float format as a trick


Pow(x, n)
Implement pow(x, n).
Iterative


Recursive


Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.


Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.


Finding nth Finobacci number in O(log n)
Finding the nth Fibonacci number using dynamic programming runs in O(n) time. There is still a better method to find F(n), when n become as large as 10^18 (as F(n) can be very huge, all we want is to find the F(N)%MOD , for a given MOD). Consider the Fibonacci recurrence F(n+1) = F(n) + F(n1). We can represent this in the form a matrix here.
Look at the matrix A = [ [ 1 1 ] [ 1 0 ] ] . Multiplying A with [ F(n) F(n1) ] gives us [ F(n+1) F(n) ] , so.. We start with [ F(1) F(0) ] , multiplying it with An gives us [ F(n+1) F(n) ] , so all that is left is finding the nth power of the matrix A. Well, this can be computed in O(log n) time, by recursive doubling. The idea is, to find An , we can do R = An/2 x An/2 and if n is odd, we need do multiply with an A at the end.


Combinatorics
Another problem might also encounter big integer is to select k gifts from n, normally we could achieve an efficient solution as follows.


Always welcome new ideas and practical
tricks, just leave them in the comments!