1304. Algorithm - Useful Math KnowledgeMath and GCD

Useful math knowledge for algorithm problems.

1. Formulas

1.1 Sum of Integers 1 through N

Q: What is 1 + 2 + 3 + … + n?
A: Sum = n(n + 1)/2

Proofs:

• n is even
#pair a b sum
1 1 n 1+n
2 2 n-1 1+n
3 3 n-2 1+n
n/2 n/2 n/2 + 1 1+n

Sum = n/2 * (n + 1)

• n is odd

Take n out of the list, pair the rest.

#pair a b sum
1 1 n-1 n
2 2 n-2 n
3 3 n-3 n
(n-1)/2 (n-1)/2 (n-1)/2 + 1 n

Sum = (n-1)/2 * n + n = n(n + 1)/2

Or, use the above conclusion for even, 1 + 2 + 3 + … + n = 1 + 2 + 3 + … + (n-1) + n = (n-1)/2 * (n - 1 + 1) + n = n(n + 1)/2.

1.2 Sum of Powers of 2

Q: What is 2^0 + 2^1 + 2^2 + … + 2^n?
A: 2^(n+1) - 1

Proofs: Look at these values in binary way.

Power Binary Decimal
2^0 00001 1
2^1 00010 2
2^2 00100 4
2^3 01000 8
2^4 10000 16
Sum 2^5-1 11111 32 - 1

Sum = 2^(n+1) - 1

1.3 GCD(greatest common divisor)

private int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}


All common divisors of two given numbers.

// method to calculate all common divisors of two given numbers
private List<Integer> commDiv(int a, int b)
{
Set<Integer> set = new HashSet();
// find gcd of a, b
int n = gcd(a, b);

for (int i = 1; i <= Math.sqrt(n); i++) {
// if 'i' is factor of n
if (n % i == 0) {
// check if divisors are equal
if (n / i == i) {
} else {
}
}
}
return new ArrayList<>(set);
}


All dividers of the given number.

private List<Integer> divider(int num)
{
List<Integer> list = new ArrayList<>();
for (int i = 1; i < num; i++) {
if (num % i == 0) {
}
}
return list;
}


1.4 Valid Perfect Square(leetcode 367)

// Newton Method
public boolean isPerfectSquare(int num) {
long x = num;
while (x * x > num) {
x = (x + num / x) >> 1;
}
return x * x == num;
}


1.5 Check Integer is Prime

Prime number: 2,3,5,7,11,13,17,19,23,29 …

Naive approach.

// time: O(n)
private boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}


Improved by setting the ceiling to square root of n, see here.

 // time: sqrt(n)
private boolean isPrime(int n) {
if (n < 2) {
return false;
}
int sqrt = (int)Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}


Same idea but without using sqrt.

// time: sqrt(n)
private boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}


4. Keywords

Complex number = real parts and imaginary parts