### 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.

#### Sqrt implementation

Binary search method

Newton method

#### Count Numbers with Unique Digits

Given a non-negative 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, map-checking 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 non-negative 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 non-negative 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?

#### Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative 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 -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
“1 + 1” = 2
“ 2-1 + 2 “ = 3
“(1+(4+5+2)-3)+(6+8)” = 23

#### 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

#### Count Primes

Count the number of prime numbers less than a non-negative number, n.

#### 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

#### 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.

#### 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.

#### 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).

#### 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(n-1). 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(n-1) ] 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!