Math

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.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class 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 3
    if(x+y < z) return false;
    //in case of zero
    if(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

1
2
3
4
5
6
7
8
9
int sqrt(int num) {
long l = 0, r = num, m = 0;
while(l < r) {
m = l+(r-l)/2;
if(m*m < num) l = m+1;
else r = m;
}
return r;
}

Newton method

1
2
3
4
int sqrt(int num) {
long g = num;
while(g*g > num) g = (g+num/g)>>1;
}

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

1
2
3
4
5
6
7
8
9
10
11
//(1-digit 10, 2-digit 91 = 9*9+10, 3-digit 739=9*9*8+9*9+10)
int countNumbersWithUniqueDigits(int n) {
if(n == 0) return 1;
int sum = 10;
for(int i = 2; i <= n; ++i) {
int t = 9;
for(int j = 0; j < i-1; ++j) t *= (9-j);
sum += t;
}
return sum;
}

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)

1
2
3
bool isPowerOfThree(int n) {
return n>0 && 1162261467%n==0;
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int nthSuperUglyNumber(int n, vector<int>& primes) {
int size = primes.size();
int indexes[size]{0}; //follow its corresponding index always;
vector<int> v(1,1);
for(int i = 1; i < n; ++i) {
int localMin = INT_MAX;
for(int j = 0; j < size; ++j)
localMin = min(localMin, primes[j]*v[indexes[j]]);
v.push_back(localMin);
for(int j = 0; j < size; ++j) //follow its corresponding index always;
if(localMin == primes[j]*v[indexes[j]]) indexes[j]++;
}
return v.back();
}

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”

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
const vector<string> numerals{"Billion", "Million", "Thousand", "Hundred", "Ninety","Eighty", "Seventy","Sixty", "Fifty", "Forty", "Thirty", "Twenty", "Nineteen", "Eighteen", "Seventeen", "Sixteen", "Fifteen", "Fourteen", "Thirteen", "Twelve","Eleven", "Ten","Nine", "Eight", "Seven", "Six", "Five", "Four", "Three","Two", "One"};
const vector<int> units = {1000000000, 1000000, 1000, 100, 90, 80, 70, 60,50, 40,30,20,19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
public:
string numberToWords(int num) {
if(num == 0) return "Zero";
int i = 0;
for(; num < units[i]; ++i) ;
int upper = num/units[i];
int lower = num%units[i];
return (i<4? numberToWords(upper) + " " : "") + numerals[i] + (lower? " " + numberToWords(lower) : "");
}
};

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?

Basic
1
2
3
4
5
6
7
8
9
10
11
12
int addDigits(int num) {
int sum = num;
while(sum >= 10){
num = sum;
sum = 0;
while(num){
sum += num%10;
num /= 10;
}
}
return sum;
}
Trick
1
2
3
int addDigits(int num) {
return num? (num%9? num%9:9) : num;
}

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.

1
2
3
4
5
6
7
8
9
10
//permutation and combination problem;
int countDigitOne(int n) {
int sum = 0;
for(long i = 1; i <= n; i *= 10) {
int a = n/i;
int b = n%i;
sum += (a+8)/10*i+(a%10==1? b+1 : 0);
}
return sum;
}

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

Iterative method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int calculate(string s) {
stack<int> sums, signs;
int sum = 0, sign = 1, num = 0;;
for(int i = 0; s[i]; ++i) {
if(isdigit(s[i])) num = 10*num+s[i]-'0';
else {
sum += sign*num;
num = 0;
if(s[i]=='+' || s[i]==' ') sign = 1;
else if(s[i] == '-') sign = -1;
else if(s[i] == '(') { sums.push(sum), signs.push(sign); sum = 0, sign = 1; }
else if(s[i] == ')') { sum = sums.top()+sum*signs.top(); sums.pop(), signs.pop(); }
}
}
return sum+sign*num;
}
Recursive method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
int calculate(string& s, int& pos) {//reference to pos tracking the index;
int sum = 0;
int sign = 1;
while(pos<s.length() && s[pos]!=')') {
if(s[pos]=='+' || s[pos]==' ') pos++, sign = 1;
else if(s[pos] == '-') pos++, sign = -1;
else if(s[pos] == '(') { pos++; sum += sign*calculate(s, pos); }
else {
int num = 0;
while(isdigit(s[pos])) num = 10*num + s[pos++]-'0';
sum += sign*num;
}
}
pos++; //move over the ')';
return sum;
}
public:
int calculate(string s) {
int pos = 0;
return calculate(s, pos);
}
};

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.

1
2
3
4
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int lMax = max(A, E), rMin = min(C, G), bMax = max(B, F), tMin = min(D, H);
return (D-B)*(C-A)+(G-E)*(H-F) - ((B>H || F>D || E>C || A>G)? 0 : (rMin-lMax)*(tMin-bMax));
}

Factorial Trailing Zeroes

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

1
2
3
4
5
6
int trailingZeroes(int n) {
int count = 0;
for(long i = 5; i <= n; i *= 5)
count += n/i;
return count;
}

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
int square(int n) {
int a = 0;
while(n) {
a += (n%10)*(n%10);
n /= 10;
}
return a;
}
public:
bool isHappy(int n) {
int slow = square(n), fast = square(square(n));
while(slow != fast) {
slow = square(slow);
fast = square(square(fast));
}
return slow == 1;
}
};
Trick
1
2
3
4
5
6
7
8
9
10
11
12
13
//in [0, 9] there are only 1 and 7 that are happy numbers;
int isHappy(int n)
{
while(n > 6) {//once it's less than 6 and if it's not 1, it must be unhappy number;
int next = 0;
while(n) {//calculate the square sum;
next += (n%10)*(n%10);
n /= 10;
}
n = next;
}
return n == 1;
}

Count Primes

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

Basic method
1
2
3
4
5
6
7
8
9
10
11
12
int countPrimes(int n) {
if(n < 3) return 0;
vector<bool> numbers(n, true);
numbers[0] = numbers[1] = false;
for(int i = 2; i <= sqrt(n); i++)
for(int j = i*i; j < n; j += i)
if(numbers[j]) numbers[j] = false;
int count = 0;
for(auto i: numbers)
if(i) count++;
return count;
}
Optimized method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int countPrimes(int n) {
if(!n || n==1) return 0;
bool *numbers = new bool[n];
memset(numbers, 1, sizeof(bool)*n);
int count = n/2; //only odd numbers should be considered;
for(int i = 3; i <= sqrt(n); i += 2) {
if(numbers[i]) {
for(int j = i*i, k = i<<1; j < n; j += k) {
if(numbers[j]) count--;
numbers[j] = false;
}
}
}
return count;
}

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
1
2
3
4
5
6
7
8
string convertToTitle(int n) {
string s;
while(n) {
s = string(1, 'A'+(n-1)%26) + s; //make it start from 0 instead of 1
n = (n-1)/26;
}
return s;
}
Recursive
1
2
3
string convertToTitle(int n) {
return ((n-1)/26? convertToTitle((n-1)/26) : "") + string(1, 'A'+(n-1)%26);
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string fractionToDecimal(int n, int d) {
string s;
int i = 0;
if(!n) return "0";
if(n<0 ^ d<0) s += "-";
long numerator = fabs(long(n)), denominator = fabs(long(d));
s += to_string(numerator/denominator);
numerator %= denominator;
if(numerator) s += ".";
unordered_map<int, int> pos_map;
i = s.length()-1;
while(numerator) {
if(pos_map.count(numerator)) {
s.insert(pos_map[numerator], "(");
s += ")";
break;
}
pos_map[numerator] = ++i;
numerator *= 10;
s += to_string(numerator/denominator);
numerator %= denominator;
}
return s;
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int myAtoi(string str) {
int i = 0;
int sign = 1;
long num = 0;
while(isspace(str[i])) i++;
if(str[i]=='-' || str[i]=='+') {
if(str[i] == '-') sign *= -1;
i++;
}
while(str[i]=='0') i++;
while(isdigit(str[i])) {
num = 10*num + str[i++]-'0';
if(num > fabs(long(INT_MIN))) break;
}
num *= sign;
if(num < INT_MIN) return INT_MIN;
if(num > INT_MAX) return INT_MAX;
return num;
}

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
1
2
3
4
5
6
7
8
9
10
11
string intToRoman(int num) {
string s, table[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int units[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
for(int i = 0; i < sizeof(units)/sizeof(int); ++i) {
while(num >= units[i]) {
s += table[i];
num -= units[i];
}
}
return s;
}
Mapping
1
2
3
4
5
6
7
8
9
10
11
12
string intToRoman(int num) {
string s;
string M[] = {"", "M", "MM", "MMM"};
string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
s += M[num/1000];
s += C[(num%=1000)/100];
s += X[(num%=100)/10];
s += I[(num%10)];
return s;
}

Roman to Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
//AC - 60ms - from left to right using unordered_map;
int romanToInt(string s) {
unordered_map<char, int> roman_map { { 'I' , 1 },{ 'V' , 5 },{ 'X' , 10 },
{ 'L' , 50 }, { 'C' , 100 }, { 'D' , 500 }, { 'M' , 1000 } };
int pre = 1, cur = 1, sum = 0;
for(int i = s.length()-1; i >= 0; --i) {
cur = roman_map[s[i]];
if(cur < pre) sum -= cur;
else sum += cur, pre = cur;
}
return sum;
}
//AC - 36ms - from right to left and using array to accelerate searching;
int romanToInt(string s) {
if (s.empty()) return 0;
int roman_map[24] = {};
roman_map['I' - 'A'] = 1;
roman_map['V' - 'A'] = 5;
roman_map['X' - 'A'] = 10;
roman_map['L' - 'A'] = 50;
roman_map['C' - 'A'] = 100;
roman_map['D' - 'A'] = 500;
roman_map['M' - 'A'] = 1000;
auto sum = 0;
auto right = roman_map[s.front() - 'A'];
for (int i = 1; i < s.size(); ++i) {
auto curr = right;
right = roman_map[s[i] - 'A'];
if (right > curr) sum -= curr;
else sum += curr;
}
return sum + right;
}
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int divide(int dividend, int divisor) {
if((dividend==INT_MIN && divisor==-1) || divisor==0) return INT_MAX;
int sign = (dividend<0 ^ divisor<0)? -1 : 1;
long dd = abs((long)dividend), dv = abs((long)divisor);
if(dd < dv) return 0;
int h = 0;
long t = dv;
while(t <= dd) t <<= 1, h++;
long ret = 1 << --h;
dd -= (t>>=1);
while(dd >= dv) {
while(t > dd)
t >>= 1, h--;
ret |= 1<<h;
dd -= t;
}
return ret*sign;
}

Trick using div, still log can also do the same

1
2
3
4
5
int divide(int dividend, int divisor) {
if(dividend==INT_MIN && divisor==-1) return INT_MAX;
div_t divresult = div(dividend, divisor);
return divresult.quot;
}

Add Binary

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

1
2
3
4
5
6
7
8
9
10
11
string addBinary(string a, string b) {
string s;
int i = a.length()-1, j = b.length()-1, c = 0;
while(i>=0 || j>=0) {
c += i>=0? a[i--]-'0':0;
c += j>=0? b[j--]-'0':0;
s = char(c%2+'0') + s;
c /= 2;
}
return c? "1"+s : s;
}

Palindrome Number

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

Basic
1
2
3
4
5
6
7
8
9
bool isPalindrome(int x) {
if(x < 0) return false;
long a = 0, t = x;
while(t) {
a = 10*a + t%10;
t /= 10;
}
return a == x;
}
Trick
1
2
3
4
5
6
7
8
9
bool isPalindrome(int x) {
if(x<0 || (x>0 && x%10==0)) return false;
int a = 0;
while(a < x) {
a = 10*a + x%10;
x /= 10;
}
return a>x? a/10==x : a==x;
}

Valid Number

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isNumber(string s) {
int i = 0, digit_count = 0, dot_count = 0;
while(s[i] == ' ') i++;
if(s[i]=='+' || s[i]=='-') i++;
while(isdigit(s[i]) || s[i]=='.') s[i++]=='.'? dot_count++ : digit_count++;
if(dot_count>1 || digit_count<1) return false;
if(s[i] == 'e') {
i++;
dot_count = digit_count = 0;
if(s[i]=='+' || s[i]=='-') i++;
while(isdigit(s[i]) || s[i]=='.') s[i++]=='.'? dot_count++ : digit_count++;
if(dot_count>0 || digit_count<1) return false;
}
while(s[i] == ' ') i++;
return s[i] == '\0';
}

Use strtof to handle float format as a trick

1
2
3
4
5
6
7
8
9
10
11
bool isNumber(string s) {
char *pEnd, *str = (char*)s.c_str();
while(*str == ' ') str++;
if(*str == '\0') return false;
float f = strtof(str, &pEnd);
//Reference to an already allocated object of type char*,
//whose value is set by the function to the next character
//in str after the numerical value.
while(*pEnd == ' ') pEnd++;
return *pEnd == '\0';
}

Pow(x, n)

Implement pow(x, n).

Iterative
1
2
3
4
5
6
7
8
9
10
11
12
double myPow(double x, int m) {
long n = m;
if(n == 0) return 1;
if(n < 0) n *= -1, x = 1/x;
double unit = x, ret = 1;
while(n) {
if(n & 1) ret *= unit;
unit *= unit; //updated each time;
n >>= 1;
}
return ret;
}
Recursive
1
2
3
4
5
6
7
double myPow(double x, int m) {
long n = m; //in case of INT_MIN;
if(n < 0) x = 1/x, n *= -1;
if(n == 0) return 1;
if(n == 1) return x;
return n%2? x*myPow(x*x, n/2) : myPow(x*x, n/2);
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string getPermutation(int n, int k) {
int i = 1, j = 0, p = 1;
string s;
for(; i <= n; ++i) {
p *= i;
s += char('0'+i);
}
for(i = 0, k--; i < n; ++i) {
p /= n-i;
j = i + k/p;
char c = s[j];
for(; j > i; --j) s[j] = s[j-1];
s[i] = c;
k %= p;
}
return s;
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxPoints(vector<Point>& points) {
int globalMax = 0, duplicates = 1;
unordered_map<double, int> slopes;
for(int i = 0; i < points.size(); ++i) {
slopes.clear();
duplicates = 1;
for(int j = i+1; j < points.size(); ++j) {
if(points[i].x==points[j].x && points[i].y==points[j].y) duplicates++;
else {
if(points[i].x==points[j].x) slopes[INT_MAX]++;
else slopes[(double)(points[j].y-points[i].y)/(points[j].x-points[i].x)]++;
}
}
int localMax = 0;
for(auto& pair: slopes) localMax = max(pair.second, localMax);
globalMax = max(globalMax, localMax+duplicates);
}
return globalMax;
}

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

1
2
3
4
5
6
7
Matrix findNthPower(Matrix M , power n) {
if( n == 1 ) return M;
Matrix R = findNthPower(M , n/2);
R = RxR; // matrix multiplication
if(n%2 == 1) R = RxM; // matrix multiplication
return R;
}

Combinatorics

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

1
2
3
4
5
6
7
8
9
unsigned long long choose(unsigned long long n, unsigned long long k) {
if (k > n) return 0;
unsigned long long r = 1;
for (unsigned long long d = 1; d <= k; ++d) {
r *= n--;
r /= d;
}
return r;
}

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