Add, Subtract, Multiplication, Division


How do you implement a function to add two integers without utilization of arithmetic +, -, *, and / operators?
Bit operations The first step is to add digits without carries. The results are 0 when adding 0 and 0, as well as adding 1 and 1. The results are 1 when adding 0 and 1, as well as 1 and 0. Note that these results are the same as bitwise XOR operations. The bitwise XOR results of 0 and 0, as well as 1 and 1, are 0, while the XOR results of 0 and 1, as well as 1 and 0, are 1. The second step is for carries. There are no carries while adding 0 and 0, 0 and 1, as well as 1 and 0. There is a carry only when 1 and 1 are added. These results are the same as bitwise AND operations. Additionally, we have to shift carries to the left for one bit to get the actual carry value. The third step is to add results of the first two steps. The adding operations can be replaced with bit operations again. These two steps above are repeated until there are carries. int add(int num1, int num2) {
    int sum, carry;
    do {
        sum = num1 ^ num2;
        carry = (num1 & num2) << 1;
        num1 = sum;
        num2 = carry;
    } while (num2 != 0);

    return num1;
}
How do you implement a function for the subtraction operation without utilization of arithmetic +, -, *, and / operators?
-b can be gotten with bit operations because -b=~b+1.
int subtract(int num1, int num2) {
    num2 = add(~num2, 1);
    return add(num1, num2);
}
How do you implement a function for the multiplication operation without utilization of arithmetic +, -, *, and / operators?
a×n can be implemented with a left-shift and additions. Since there are O(logn) 1 bits in the binary representation of n, the new solution invokes the add method for O(logn) times.
int multiply(int num1, int num2) {
    boolean minus = false;
    if ((num1 < 0 && num2 > 0) || (num1 > 0 && num2 < 0))
        minus = true;

    if (num1 < 0)
        num1 = add(~num1, 1);
    if (num2 < 0)
        num2 = add(~num2, 1);

    int result = 0;
    while (num1 > 0) {
        if ((num1 & 0x1) != 0) {
            result = add(result, num2);
        }

        num2 = num2 << 1;
        num1 = num1 >> 1;
    }

    if (minus)
        result = add(~result, 1);

    return result;
}
How do you implement a function to divide an integer by another without utilization of arithmetic +, -, *, and / operators?

Array Construction
void multiply(double array1[], double array2[]){
    if(array1.length == array2.length && array1.length > 0){
        array2[0] = 1;
        for(int i = 1; i < array1.length; ++i){
            array2[i] = array2[i - 1] * array1[i - 1];
        }

        int temp = 1;
        for(int i = array1.length - 2; i >= 0; --i){
            temp *= array1[i + 1];
            array2[i] *= temp;
        }
    }
}
The time complexity of this solution is O(n) obviously

Greatest Common Divisor (GCD) and Least Common Multiple (LCM) Algorithm


https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm
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.
The Euclidean Algorithm makes use of these properties by rapidly reducing the problem into easier and easier problems, using the third property,  until it is easily solved by using one of the first two properties.
We can understand why these properties work by proving them.
We can prove that GCD(A,0)=A is as follows:


  • The largest integer that can evenly divide A is A.
  • All integers evenly divide 0, since for any integer, C, we can write C ⋅ 0 = 0. So we can conclude that A must evenly divide 0.
  • The greatest number that divides both A and 0 is A.


Suppose we have three integers A,B and C such that A-B=C.
Proof that the GCD(A,B) evenly divides C
The GCD(A,B), by definition, evenly divides A. As a result, A must be some multiple of GCD(A,B). i.e. X⋅GCD(A,B)=A where X is some integer
The GCD(A,B), by definition, evenly divides B. As a result,  B must be some multiple of GCD(A,B). i.e. Y⋅GCD(A,B)=B where Y is some integer
A-B=C gives us:
  • X⋅GCD(A,B) - Y⋅GCD(A,B) = C
  • (X - Y)⋅GCD(A,B) = C
So we can see that GCD(A,B) evenly divides C.
An illustration of this proof  is shown in the left portion of the figure below:
Proof that the GCD(B,C) evenly divides A
The GCD(B,C), by definition, evenly divides B. As a result, B must be some multiple of GCD(B,C). i.e. M⋅GCD(B,C)=B where M is some integer
The GCD(B,C), by definition, evenly divides C. As a result,  C must be some multiple of GCD(B,C). i.e. N⋅GCD(B,C)=C where N is some integer
A-B=C gives us:
  • B+C=A
  • M⋅GCD(B,C) + N⋅GCD(B,C) = A
  • (M + N)⋅GCD(B,C) = A
So we can see that GCD(B,C) evenly divides A.
An illustration of this proof  is shown in the figure below
Proof that GCD(A,B)=GCD(A,A-B)
  • GCD(A,B) by definition, evenly divides B.
  • We proved that GCD(A,B) evenly divides C.
  • Since the GCD(A,B) divides both B and C evenly it is a common divisor of B and C.
GCD(A,B) must be less than or equal to, GCD(B,C), because GCD(B,C) is the “greatest” common divisor of B and C.
  • GCD(B,C) by definition, evenly divides B.
  • We proved that GCD(B,C) evenly divides A.
  • Since the GCD(B,C) divides both A and B evenly it is a common divisor of A and B.
GCD(B,C) must be less than or equal to, GCD(A,B), because GCD(A,B) is the “greatest” common divisor of A and B.
Given that GCD(A,B)≤GCD(B,C) and GCD(B,C)≤GCD(A,B) we can conclude that:
GCD(A,B)=GCD(B,C)
Which is equivalent to:
GCD(A,B)=GCD(B,A-B)
An illustration of this proof  is shown in the right portion of the figure below.
Proof that GCD(A,B) = GCD(B,R)
We proved that GCD(A,B)=GCD(B,A-B)
The order of the terms does not matter so we can say GCD(A,B)=GCD(A-B,B)
We can repeatedly apply GCD(A,B)=GCD(A-B,B) to obtain:
GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)=GCD(A-3B,B)=...=GCD(A-Q⋅B,B)
But A= B⋅Q + R so  A-Q⋅B=R
Thus GCD(A,B)=GCD(R,B)
The order of terms does not matter, thus:
GCD(A,B)=GCD(B,R)
http://quiz.geeksforgeeks.org/c-program-find-gcd-hcf-two-numbers/
int gcd(int a, int b)
{
    // Everything divides 0
    if (a == 0 || b == 0)
       return 0;
    // base case
    if (a == b)
        return a;
    // a is greater
    if (a > b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}
http://www.geeksforgeeks.org/euclids-algorithm-when-and-operations-are-costly/
Version 1 (Using subtraction)
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
    if (a == b) 
       return a;
  
    return (a > b)? gcd(a-b, b): gcd(a, b-a);
}
Version 2 (Using modulo operator)
int gcd(int a, int b)
{
    if (a == 0)
       return b;
     
    return gcd(b%a, a);
}
Version 1 can take linear time to find the GCD, consider the situation when one of the given numbers is much bigger than the other. Version 2 is obviously more efficient as there are less recursive calls and takes logarithmic time.
Below are some important observations. The idea is to use bitwise operators. We can find x/2 using x>>1. We can check whether x is odd or even using x&1.
gcd(a, b) = 2*gcd(a/2, b/2) if both a and b are even.
gcd(a, b) = gcd(a/2, b) if a is even and b is odd.
gcd(a, b) = gcd(a, b/2) if a is odd and b is even.
int gcd(int a, int b)
{
    // Base cases
    if (b == 0 || a == b) return a;
    if (a == 0) return b;
    // If both a and b are even, divide both a
    // and b by 2.  And multiply the result with 2
    if ( (a & 1) == 0 && (b & 1) == 0 )
       return gcd(a>>1, b>>1) << 1;
    // If a is even and b is odd, divide a bb 2
    if ( (a & 1) == 0 && (b & 1) != 0 )
       return gcd(a>>1, b);
    // If a is odd and b is even, divide b bb 2
    if ( (a & 1) != 0 && (b & 1) == 0 )
       return gcd(a, b>>1);
    // If both are odd, then apply normal subtraction
    // algorithm.  Note that odd-odd case always
    // converts odd-even case after one recursion
    return (a > b)? gcd(a-b, b): gcd(a, b-a);
}

http://qiemengdao.iteye.com/blog/1660212
和欧几里德算法 算法不同的是,Stein算法只有整数的移位和加减法
gcd(a,a) = a,也就是一个数和他自身的公约数是其自身 
gcd(ka,kb) = k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换,特殊的,当k=2时,说明两个偶数的最大公约数必然能被2整除。

有了上述规律就可以给出Stein算法如下:
如果A=0,B是最大公约数,算法结束
如果B=0,A是最大公约数,算法结束
设置A1 = A、B1=B和C1 = 1
如果An和Bn都是偶数,则An+1 =An /2,Bn+1 =Bn /2,Cn+1 =Cn *2(注意,乘2只要把整数左移一位即可,除2只要把整数右移一位即可)
如果An是偶数,Bn不是偶数,则An+1 =An /2,Bn+1 =Bn ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
如果Bn是偶数,An不是偶数,则Bn+1 =Bn /2,An+1 =An ,Cn+1 =Cn (很显然啦,2不是奇数的约数)
如果An和Bn都不是偶数,则An+1 =|An -Bn|,Bn+1 =min(An,Bn),Cn+1 =Cn
n++,转4 
intGcd(inta,intb)
{
if(a==0)returnb;
if(b==0)returna;
if(a%2==0&&b%2==0)return2*gcd(a>>1,b>>1);
elseif(a%2==0)returngcd(a>>1,b);
elseif(b%2==0)returngcd(a,b>>1);
elsereturngcd(abs(a-b),Min(a,b));
}

考虑欧几里德算法,最恶劣的情况是,每次迭代a = 2b -1,这样,迭代后,r= b-1。如果a小于2N,这样大约需要 4N次迭代。而考虑Stein算法,每次迭代后,显然AN+1BN+1≤ ANBN/2,最大迭代次数也不超过4N次。也就是说,迭代次数几乎是相等的。但是,需要注意的是,对于大素数,试商法将使每次迭代都更复杂,因此对于大素数Stein将更有优势

Binary GCD algorithm
http://en.wikipedia.org/wiki/Binary_GCD_algorithm
Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. 
The algorithm reduces the problem of finding the GCD by repeatedly applying these identities:
gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.
If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u ? v)/2, v). If both are odd and u &lt; v, then gcd(u, v) = gcd((v ? u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.[3]
Repeat steps 2–4 until u = v, or (one more step) until u = 0. In either case, the GCD is 2kv, where k is the number of common factors of 2 found in step 2.
The algorithm requires O(n2)[4] worst-case time, where n is the number of bits in the larger of the two numbers. Although each step reduces at least one of the operands by at least a factor of 2, the subtract and shift operations take linear time for very large integers (although they're still quite fast in practice, requiring about one operation per word of the representation).
Recursive version in C
unsigned int gcd(unsigned int u, unsigned int v)
{
    // simple cases (termination)
    if (u == v)
        return u;

    if (u == 0)
        return v;

    if (v == 0)
        return u;

    // look for factors of 2
    if (~u & 1) // u is even
    {
        if (v & 1) // v is odd
            return gcd(u &gt;&gt; 1, v);
        else // both u and v are even
            return gcd(u &gt;&gt; 1, v &gt;&gt; 1) &lt;&lt; 1;
    }

    if (~v & 1) // u is odd, v is even
        return gcd(u, v &gt;&gt; 1);

    // reduce larger argument
    if (u &gt; v)
        return gcd((u - v) &gt;&gt; 1, v);

    return gcd((v - u) &gt;&gt; 1, u);
}
Iterative version in C
It first removes all common factors of 2 using identity 2, then computes the GCD of the remaining numbers using identities 3 and 4, and combines these to form the final answer.

with implementations of binary GCD similar to the above C code, the gain in speed over the Euclidean algorithm is always less in practice than in theory. The reason is that the code uses many data-dependent branches

https://github.com/adnanaziz/EpiCode/blob/master/Java/com/epi/GCD.java

Euclid's GCD Algorithm欧几里得
http://people.cis.ksu.edu/~schmidt/301s12/Exercises/euclid_alg.html
http://en.wikipedia.org/wiki/Euclidean_algorithm
Euclid's insight was to observe that, if x &gt; y, then
GCD(x,y) = GCD(x-y,y)
Proof:
x - y = q1d - q2d = (q1 - q2)d. Therefore d is also a divisor of x-y.
Using similar reasoning, one can show the converse, i.e., that any divisor of x-y and y is also a divisor of x. Hence, the set of common divisors of x and y is the same as the set of common divisors of x-y and y. In particular, the largest values in these two sets are the same, which is to say that GCD(x,y) = GCD(x-y,y).
int gcd(int K, int M) {
      int k = K;   // In order to state a simple, elegant loop invariant,
      int m = M;   // we keep the formal arguments constant and use 
                   // local variables to do the calculations.
      // loop invariant: GCD(K,M) = GCD(k,m)
      while (k != m) {
         if (k &gt; m) 
            { k = k-m; }
         else 
            { m = m-k; }
      }
      // At this point, GCD(K,M) = GCD(k,m) = GCD(k,k) = k
      return k;
}
A significant improvement in performance (in some cases) is possible, however, by using the remainder operator (%) rather than subtraction.
   int gcd(int K, int M) {
      int k = K;   // In order to state a simple, elegant loop invariant,
      int m = M;   // we keep the formal arguments constant and use 
                   // local variables to do the calculations.
      // loop invariant: GCD(K,M) = GCD(k,m)
      while (k !=0  &&  m != 0) {
         if (k &gt; m)
            { k = k % m; }
         else
            { m = m % k; }
      }
      // At this point, GCD(K,M) = GCD(k,m) = max(k,m)
      return Math.max(k,m);
   }
Further code-simplification improvements are possible, however, by ensuring that k ≥ m. We can achieve this by replacing, on each iteration, k's value by m's and m's by k % m. This way, no if statement is needed:


   int gcd(int K, int M) {
      int k = Math.max(K,M);
      int m = Math.min(K,M);
      // loop invariant: k ≥ m ∧ GCD(K,M) = GCD(k,m)
      while (m != 0) {
         int r = k % m;
         k = m;
         m = r;
      }
      // At this point, GCD(K,M) = GCD(k,m) = GCD(k,0) = k
      return k;
   }
http://rosettacode.org/wiki/Least_common_multiple
If you already have gcd for greatest common divisor, then this formula calculates lcm.
\operatorname{lcm}(m, n) = \frac{|m \times n|}{\operatorname{gcd}(m, n)}
One can also find lcm by merging the prime decompositions of both m and n.


Computing the least common multiple of an integer array, using the associative law:

\operatorname{lcm}(a,b,c)=\operatorname{lcm}(\operatorname{lcm}(a,b),c),
\operatorname{lcm}(a_1,a_2,\ldots,a_n) = \operatorname{lcm}(\operatorname{lcm}(a_1,a_2,\ldots,a_{n-1}),a_n).
function LCM(A)  // A is an integer array (e.g. [-50,25,-45,-18,90,447])
{   
    var n = A.length, a = Math.abs(A[0]);
    for (var i = 1; i < n; i++)
     { var b = Math.abs(A[i]), c = a;
       while (a && b){ a > b ? a %= b : b %= a; } 
       a = Math.abs(c*A[i])/(a+b);
     }
    return a;
}
http://codesam.blogspot.com/2011/04/calculate-least-common-multiple-of-two.html
Not efficient:
  int lcm(int num1, int num2)
  {
    if (num1 % num2 == 0)
      return num1;

    if (num2 % num1 == 0)
      return num2;
      
    int n = (num1 <= num2) ? num2 : num1;
    
    for (; ; n++)
    {
      if(n % num1 == 0 && n % num2 == 0)
         return n;
    }
  }
http://www.sanfoundry.com/java-program-find-gcd-lcm-two-numbers/
  1.     static int gcd(int x, int y)
  2.     {
  3.         int r=0, a, b;
  4.         a = (x > y) ? x : y; // a is greater number
  5.         b = (x < y) ? x : y; // b is smaller number
  6.  
  7.         r = b;
  8.         while(a % b != 0)
  9.         {
  10.             r = a % b;
  11.             a = b;
  12.             b = r;
  13.         }
  14.         return r;
  15.     }
  16.  
  17.     static int lcm(int x, int y)
  18.     {
  19.         int a;
  20.         a = (x > y) ? x : y; // a is greater number
  21.         while(true)
  22.         {
  23.             if(a % x == 0 && a % y == 0)
  24.                 return a;
  25.             ++a;
  26.         } 
  27.     }
http://massivealgorithms.blogspot.com/2014/09/aoj-0005-gcd-and-lcm.html
long long gcd(long long a, long long b)
{
    if (b == 0)return a;
    return gcd(b, a%b);
}

long long lcm(long long a, long long b)
{
    return a * b / gcd(a, b);
}


gcd(M, N) × lcm(M, N) = M × N.
It follows that to find one is sufficient to find another, for example, gcd(N, M) = N × M / lcm(N, M). gcd alone can be found with Euclid's algorithm; lcm of two or more numbers is produced by the onion algorithm.
http://www.geeksforgeeks.org/steins-algorithm-for-finding-gcd/
  1. If both and b are 0, gcd is zero gcd(0, 0) = 0.
  2. gcd(a, 0) = a and gcd(0, b) = b because everything divides 0.
  3. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
  4. If a is even and b is odd, gcd(a, b) = gcd(a/2, b). Similarly, if a is odd and b is even, then
    gcd(a, b) = gcd(a, b/2). It is because 2 is not a common divisor.
  5. If both a and b are odd, then gcd(a, b) = gcd(|a-b|/2, b). Note that difference of two odd numbers is even
  6. Repeat steps 3–5 until a = b, or until a = 0. In either case, the GCD is power(2, k) * b, where power(2, k) is 2 raise to the power of k and k is the number of common factors of 2 found in step 2.

Time Complexity: O(N*N) where N is the number of bits in the larger number.
References:
int gcd(int a, int b)
{
    if (a == b)
        return a;
    /* GCD(0,b) == b; GCD(a,0) == a, GCD(0,0) == 0 */
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    // look for factors of 2
    if (~a & 1 )        // a is even
    {
        if (b & 1)      // b is odd
            return gcd(a >> 1, b);
        else            // both a and b are even
            return gcd(a >> 1, b >> 1) << 1;
    }
    if (~b & 1)         // a is odd, b is even
        return gcd(a, b >> 1);
    // reduce larger number
    if (a > b)
        return gcd((a - b) >> 1, b);
    return gcd((b - a) >> 1, a);
}

int gcd(int a, int b)
{
    /* GCD(0, b) == b; GCD(a,0) == a, GCD(0,0) == 0 */
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    /*Finding K, where K is the greatest power of 2
      that divides both a and b. */
    int k;
    for (k = 0; ((a | b) & 1) == 0; ++k)
    {
        a >>= 1;
        b >>= 1;
    }
    /* Dividing a by 2 until a becomes odd */
    while ((a & 1) == 0)
        a >>= 1;
    /* From here on, 'a' is always odd. */
    do
    {
        /* If b is even, remove all factor of 2 in b */
        while ((b & 1) == 0)
            b >>= 1;
        /* Now a and b are both odd. Swap if necessary
           so a <= b, then set b = b - a (which is even).*/
        if (a > b)
            swap(a, b);   // Swap u and v.
        b = (b - a);
    }   while (b != 0);
    /* restore common factors of 2 */
    return a << k;
}
http://www.geeksforgeeks.org/gcd-two-array-numbers/
Given an array of numbers, find GCD of the array elements.
The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.
gcd(a, b, c) = gcd(a, gcd(b, c)) 
             = gcd(gcd(a, b), c) 
             = gcd(gcd(a, c), b)
For an array of elements, we do following.
result = arr[0]
For i = 1 to n-1
   result = GCD(result, arr[i])
int findGCD(int arr[], int n)
{
    int result = arr[0];
    for (int i=1; i<n; i++)
        result = gcd(arr[i], result);
    return result;
}

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts