Basic Maths

Power

x^7 = x (xx)^3 = x (xx) (xx)^2 = x (xx) (xx^2^(2/2))

Moduar

A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C

Shortest Distance

296. Best Meeting Point

Select a point where the sum of distance with other points is minimal. The optimal location is that point to be the median.

Programmatically, to sum up the distance could be:

|---------|----------|------------|(optimal pt)-----------------|-----|----|

int sum = 0;
int i = 0, j = list.size()-1;
while (i<j) {
    sum += list.get(j) - list.get(i);
    j--; i++;
}

Subarray Counting

713. Subarray Product Less Than K

10 5 2

10 5 2 6, when we expand one more number, the additional subarray count is [6], [6 2], [6 2 5], [6 2 5 10] = r_index - _l_index + 1.

Find intersection of two intervals

overlapped = (max(a0, b0), min(a1, b1)). If max(a0, b0) > min(a1, b1), no overlap.

case 1: b ends before a ends
a:           a0 |---------| a1
b:     b0 |---------| b1

case 2: b ends after a ends
a: a0 |--------| a1
b:     b0 |--------| b1

case 3: interval 2 is completely within interval 1.
a: a0 |--------| a1
b:     b0 |--------| b1

Traverse a Matrix with Single Index Var

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int old_r = nums.length, old_c = nums[0].length;
        if(old_r*old_c != r*c) return nums;

        int[][] result = new int[r][c];
        for(int i=0; i<old_r*old_c; i++) {
            result[i/c][i%c] = nums[i/old_c][i%old_c];
        }

        return result;
    }
}

Similarly, we can have Queue/Set of a matrix cell by encoded 1D coordinate. The id = row * width + col

353. Design Snake Game

Count How Many Common Char/Digit in Single Pass

The idea is one count+, one count-,

if + from a negative means I put back an element to match that negative;

if - from a positive means I cancel out an excessive element.

For example:

1, 2, 2 1, 3

2, 1, 1, 2, 2

if(count[nums1[i]]<0) common++;
if(count[nums2[i]]>0) common++;
count[nums1[i]]++;
count[nums2[i]]--;

Another problem that utilize this kind of counting thinking to keep track of how many characters we want is in the window.

76. Minimum Window Substring

Binary Numbers

let 2k = 111110

then k is = 11111

2k + 1 = 111111

k = 11111

Use XOR to Determine Sign of Division Result

int sign = dividend>0 ^ divisor>0? -1: 1;

Euclidean Algorithm for GCD

914. X of a Kind in a Deck of Cards

If we examine the Euclidean Algorithm we can see that it makes use of the following properties:
GCD(A,0) = A
GCD(0,B) = B
If A = B⋅Q + R and B≠0 then GCD(A,B) = GCD(B,R) where Q is an integer, R is an integer between 0 and B-1

The first two properties let us find the GCD if either number is 0. 
The third property lets us take a larger, more difficult to solve problem, and reduce it to a smaller, 
easier to solve problem.

Math