 In cryptography, a **Caesar cipher**, also known as **Caesar's cipher**, the **shift cipher**, **Caesar's code** or **Caesar shift**, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of `3`, `D` would be replaced by `A`, `E` would become `B`, and so on. The method is named after Julius Caesar, who used it in his private correspondence.    The transformation can be represented by aligning two alphabets; the cipher alphabet is the plain alphabet rotated left or right by some number of positions. For instance, here is a Caesar cipher using a left rotation of three places, equivalent to a right shift of 23 (the shift parameter is used as the key):  Plain:    ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher:   XYZABCDEFGHIJKLMNOPQRSTUVW  When encrypting, a person looks up each letter of the message in the "plain" line and writes down the corresponding letter in the "cipher" line.  Plaintext:  THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD     

caesar cipher

 The **Hill cipher** is a [polygraphic substitution](https://en.wikipedia.org/wiki/Polygraphic_substitution) cipher based on linear algebra.  Each letter is represented by a number [modulo](https://en.wikipedia.org/wiki/Modular_arithmetic) `26`. Though this is not an essential feature of the cipher, this simple scheme is often used:    To encrypt a message, each block of `n` letters (considered as an `n`-component vector) is multiplied by an invertible `n × n` matrix, against modulus `26`.  The matrix used for encryption is the _cipher key_, and it should be chosen randomly from the set of invertible `n × n` matrices (modulo `26`). The cipher can, of course, be adapted to an alphabet with any number of letters; all arithmetic just needs to be done modulo the number of letters instead of modulo `26`.  Consider the message `ACT`, and the key below (or `GYB/NQK/URP` in letters):   Since `A` is`0`, `C` is `2` and `T` is `19`, the message is the vector:   Thus, the enciphered vector is given by:   which corresponds to a ciphertext of `POH`.  Now, suppose that our message is instead `CAT` (notice how we're using the same letters as in `ACT` here), or:   This time, the enciphered vector is given by:   which corresponds to a ciphertext of `FIN`. Every letter has changed.   To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption. We turn the ciphertext back into a vector, then simply multiply by the inverse matrix of the key matrix (`IFK/VIV/VMI` in letters). (See [matrix inversion](https://en.wikipedia.org/wiki/Matrix_inversion) for methods to calculate the inverse matrix.) We find that, modulo 26, the inverse of the matrix used in the previous example is:                  -1  Taking the previous example ciphertext of `POH`, we get:   which gets us back to `ACT`, as expected.   Two complications exist in picking the encrypting matrix:  1. Not all matrices have an inverse. The matrix will have an inverse if and only if its [determinant](https://en.wikipedia.org/wiki/Determinant) is not zero. 2. The determinant of the encrypting matrix must not have any common factors with the modular base.  Thus, if we work modulo `26` as above, the determinant must be nonzero, and must not be divisible by `2` or `13`. If the determinant is `0`, or has common factors with the modular base, then the matrix cannot be used in the Hill cipher, and another matrix must be chosen (otherwise it will not be possible to decrypt). Fortunately, matrices which satisfy the conditions to be used in the Hill cipher are fairly common.    

hill cipher

**Hash functions** are used to map large data sets of elements of an arbitrary length (*the keys*) to smaller data sets of elements of a fixed length (*the fingerprints*). The basic application of hashing is efficient testing of equality of keys by comparing their fingerprints. A *collision* happens when two different keys have the same fingerprint. The way in which collisions are handled is crucial in most applications of hashing. Hashing is particularly useful in construction of efficient practical algorithms. A **rolling hash** (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly — the new hash value is rapidly calculated given only the following data: An ideal hash function for strings should obviously depend both on the *multiset* of the symbols present in the key and on the *order* of the symbols. The most common family of such hash functions treats the symbols of a string as coefficients of a *polynomial* with an integer variable `p` and computes its value modulo an integer constant `M`: The *Rabin–Karp string search algorithm* is often explained using a very simple rolling hash function that only uses multiplications and additions - **polynomial rolling hash**: > H(s0, s1, ..., sk) = s0 * pk-1 + s1 * pk-2 + ... + sk * p0 where `p` is a constant, and *(s1, ... , sk)* are the input characters. For example we can convert short strings to key numbers by multiplying digit codes by powers of a constant. The three letter word `ace` could turn into a number by calculating: > key = 1 * 262 + 3 * 261 + 5 * 260 In order to avoid manipulating huge `H` values, all math is done modulo `M`. > H(s0, s1, ..., sk) = (s0 * pk-1 + s1 * pk-2 + ... + sk * p0) mod M A careful choice of the parameters `M`, `p` is important to obtain “good” properties of the hash function, i.e., low collision rate. This approach has the desirable attribute of involving all the characters in the input string. The calculated key value can then be hashed into an array index in the usual way: function hash(key, arraySize) { const base = 13; let hash = 0; for (let charIndex = 0; charIndex < key.length; charIndex += 1) { const charCode = key.charCodeAt(charIndex); hash += charCode * (base ** (key.length - charIndex - 1)); } return hash % arraySize; } The `hash()` method is not as efficient as it might be. Other than the character conversion, there are two multiplications and an addition inside the loop. We can eliminate one multiplication by using **Horner's method*: > a4 * x4 + a3 * x3 + a2 * x2 + a1 * x1 + a0 = (((a4 * x + a3) * x + a2) * x + a1) * x + a0 In other words: > Hi = (P * Hi-1 + Si) mod M The `hash()` cannot handle long strings because the hashVal exceeds the size of int. Notice that the key always ends up being less than the array size. In Horner's method we can apply the modulo (%) operator at each step in the calculation. This gives the same result as applying the modulo operator once at the end, but avoids the overflow. function hash(key, arraySize) { const base = 13; let hash = 0; for (let charIndex = 0; charIndex < key.length; charIndex += 1) { const charCode = key.charCodeAt(charIndex); hash = (hash * base + charCode) % arraySize; } return hash; } Polynomial hashing has a rolling property: the fingerprints can be updated efficiently when symbols are added or removed at the ends of the string (provided that an array of powers of p modulo M of sufficient length is stored). The popular Rabin–Karp pattern matching algorithm is based on this property

polynomial hash

 The **rail fence cipher** (also called a **zigzag cipher**) is a [transposition cipher](https://en.wikipedia.org/wiki/Transposition_cipher) in which the message is split across a set of rails on a fence for encoding. The fence is populated with the message's characters, starting at the top left and adding a character on each position, traversing them diagonally to the bottom. Upon reaching the last rail, the direction should then turn diagonal and upwards up to the very first rail in a zig-zag motion. Rinse and repeat until the message is fully disposed across the fence. The encoded message is the result of concatenating the text in each rail, from top to bottom.  From [wikipedia](https://en.wikipedia.org/wiki/Rail_fence_cipher), this is what the message `WE ARE DISCOVERED. FLEE AT ONCE` looks like on a `3`-rail fence:  W . . . E . . . C . . . R . . . L . . . T . . . E . E . R . D . S . O . E . E . F . E . A . O . C . . . A . . . I . . . V . . . D . . . E . . . N . .              WECRLTEERDSOEEFEAOCAIVDEN  The message can then be decoded by re-creating the encoded fence, with the same traversal pattern, except characters should only be added on one rail at a time. To illustrate that, a dash can be added on the rails that are not supposed to be populated yet. This is what the fence would look like after populating the first rail, the dashes represent positions that were visited but not populated.  W . . . E . . . C . . . R . . . L . . . T . . . E . - . - . - . - . - . - . - . - . - . - . - . - . . . - . . . - . . . - . . . - . . . - . . . - . .  It's time to start populating the next rail once the number of visited fence positions is equal to the number of characters in the message.   

rail fence cipher

 A vertex in an undirected connected graph is an articulation point (or cut vertex) if removing it (and edges through it) disconnects  the graph. Articulation points represent vulnerabilities in a  connected network – single points whose failure would split the  network into 2 or more disconnected components. They are useful for  designing reliable networks.  For a disconnected undirected graph, an articulation point is a  vertex removing which increases number of connected components.      

articulation points

 The Bellman–Ford algorithm is an algorithm that computes shortest  paths from a single source vertex to all of the other vertices  in a weighted digraph. It is slower than Dijkstra's algorithm  for the same problem, but more versatile, as it is capable of  handling graphs in which some of the edge weights are negative  numbers.    Worst-case performance `O(|V||E|)` Best-case performance	`O(|E|)` Worst-case space complexity `O(|V|)`   

bellman ford

 Breadth-first search (BFS) is an algorithm for traversing  or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes  referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.    

breadth first search

 In graph theory, a **bridge**, **isthmus**, **cut-edge**, or **cut arc** is an edge  of a graph whose deletion increases its number of connected components. Equivalently,  an edge is a bridge if and only if it is not contained in any cycle. A graph is said  to be bridgeless or isthmus-free if it contains no bridges.   A graph with 16 vertices and 6 bridges (highlighted in red)   An undirected connected graph with no cut edges      

bridges

 Depth-first search (DFS) is an algorithm for traversing or  searching tree or graph data structures. One starts at  the root (selecting some arbitrary node as the root in  the case of a graph) and explores as far as possible  along each branch before backtracking.    

depth first search

 In graph theory, a **cycle** is a path of edges and vertices  wherein a vertex is reachable from itself. There are several  different types of cycles, principally a **closed walk** and  a **simple cycle**.   A **closed walk** consists of a sequence of vertices starting  and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph. In a directed graph, each edge must be traversed by the walk consistently with its direction:  the edge must be oriented from the earlier of two consecutive vertices  to the later of the two vertices in the sequence.  The choice of starting vertex is not important: traversing the same cyclic  sequence of edges from different starting vertices produces the same closed walk.  A **simple cycle may** be defined either as a closed walk with no repetitions of  vertices and edges allowed, other than the repetition of the starting and ending  vertex, or as the set of edges in such a walk. The two definitions are equivalent  in directed graphs, where simple cycles are also called directed cycles: the cyclic  sequence of vertices and edges in a walk is completely determined by the set of  edges that it uses. In undirected graphs the set of edges of a cycle can be  traversed by a walk in either of two directions, giving two possible directed cycles  for every undirected cycle. A circuit can be a closed walk allowing repetitions of  vertices but not edges; however, it can also be a simple cycle, so explicit  definition is recommended when it is used.    A graph with edges colored to illustrate **path** `H-A-B` (green), closed path or  **walk with a repeated vertex** `B-D-E-F-D-C-B` (blue) and a **cycle with no repeated edge** or  vertex `H-D-G-H` (red)       General information:   Cycles in undirected graphs:   Cycles in directed graphs:  

detect cycle

 Dijkstra's algorithm is an algorithm for finding the shortest  paths between nodes in a graph, which may represent, for example,  road networks.   The algorithm exists in many variants; Dijkstra's original variant  found the shortest path between two nodes, but a more common  variant fixes a single node as the "source" node and finds  shortest paths from the source to all other nodes in the graph,  producing a shortest-path tree.   Dijkstra's algorithm to find the shortest path between `a` and `b`. It picks the unvisited vertex with the lowest distance,  calculates the distance through it to each unvisited neighbor,  and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.   

dijkstra

 In graph theory, an **Eulerian trail** (or **Eulerian path**) is a  trail in a finite graph which visits every edge exactly once. Similarly, an **Eulerian circuit** or **Eulerian cycle** is an  Eulerian trail which starts and ends on the same vertex.  Euler proved that a necessary condition for the existence of Eulerian  circuits is that all vertices in the graph have an even degree, and  stated that connected graphs with all vertices of even degree have  an Eulerian circuit.   Every vertex of this graph has an even degree. Therefore, this is  an Eulerian graph. Following the edges in alphabetical order gives  an Eulerian circuit/cycle.  For the existence of Eulerian trails it is necessary that zero or  two vertices have an odd degree; this means the Königsberg graph  is not Eulerian. If there are no vertices of odd degree,  all Eulerian trails are circuits. If there are exactly two vertices  of odd degree, all Eulerian trails start at one of them and end at  the other. A graph that has an Eulerian trail but not an Eulerian  circuit is called semi-Eulerian.   The Königsberg Bridges multigraph. This multigraph is not Eulerian,  therefore, a solution does not exist.   

eulerian path

 In computer science, the **Floyd–Warshall algorithm** is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the  lengths (summed weights) of shortest paths between all pairs of vertices. Although  it does not return details of the paths themselves, it is possible to reconstruct  the paths with simple modifications to the algorithm.   The Floyd–Warshall algorithm compares all possible paths through the graph between  each pair of vertices. It is able to do this with `O(|V|^3)` comparisons in a graph. This is remarkable considering that there may be up to `|V|^2` edges in the graph,  and every combination of edges is tested. It does so by incrementally improving an  estimate on the shortest path between two vertices, until the estimate is optimal.  Consider a graph `G` with vertices `V` numbered `1` through `N`. Further consider  a function `shortestPath(i, j, k)` that returns the shortest possible path  from `i` to `j` using vertices only from the set `{1, 2, ..., k}` as  intermediate points along the way. Now, given this function, our goal is to  find the shortest path from each `i` to each `j` using only vertices  in `{1, 2, ..., N}`.    This formula is the heart of the Floyd–Warshall algorithm.   The algorithm above is executed on the graph on the left below:   In the tables below `i` is row numbers and `j` is column numbers.   **k = 0**    **k = 1**    **k = 2**    **k = 3**    **k = 4**    

floyd warshall

 **Hamiltonian path** (or **traceable path**) is a path in an  undirected or directed graph that visits each vertex exactly once.  A **Hamiltonian cycle** (or **Hamiltonian circuit**) is a  Hamiltonian path that is a cycle. Determining whether such paths  and cycles exist in graphs is the **Hamiltonian path problem**.   One possible Hamiltonian cycle through every vertex of a  dodecahedron is shown in red – like all platonic solids, the  dodecahedron is Hamiltonian.   Generate all possible configurations of vertices and print a  configuration that satisfies the given constraints. There  will be `n!` (n factorial) configurations.  while there are untried configurations {    generate the next configuration    if ( there are edges between two consecutive vertices of this       configuration and there is an edge from the last vertex to        the first ).    {       print this configuration;       break;    } }   Create an empty path array and add vertex `0` to it. Add other  vertices, starting from the vertex `1`. Before adding a vertex,  check for whether it is adjacent to the previously added vertex  and not already added. If we find such a vertex, we add the  vertex as part of the solution. If we do not find a vertex  then we return false.   

hamiltonian cycle

 Kruskal's algorithm is a minimum-spanning-tree algorithm which  finds an edge of the least possible weight that connects any two  trees in the forest. It is a greedy algorithm in graph theory  as it finds a minimum spanning tree for a connected weighted  graph adding increasing cost arcs at each step. This means it  finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is  minimized. If the graph is not connected, then it finds a  minimum spanning forest (a minimum spanning tree for each  connected component).    A demo for Kruskal's algorithm based on Euclidean distance.   A **minimum spanning tree** (MST) or minimum weight spanning tree  is a subset of the edges of a connected, edge-weighted  (un)directed graph that connects all the vertices together,  without any cycles and with the minimum possible total edge  weight. That is, it is a spanning tree whose sum of edge weights  is as small as possible. More generally, any edge-weighted  undirected graph (not necessarily connected) has a minimum  spanning forest, which is a union of the minimum spanning  trees for its connected components.   A planar graph and its minimum spanning tree. Each edge is  labeled with its weight, which here is roughly proportional  to its length.   This figure shows there may be more than one minimum spanning  tree in a graph. In the figure, the two trees below the graph  are two possibilities of minimum spanning tree of the given graph.   

kruskal

 In computer science, **Prim's algorithm** is a greedy algorithm that  finds a minimum spanning tree for a weighted undirected graph.   The algorithm operates by building this tree one vertex at a  time, from an arbitrary starting vertex, at each step adding  the cheapest possible connection from the tree to another vertex.   Prim's algorithm starting at vertex `A`. In the third step, edges  After that step, `AB` is no longer a candidate for addition  to the tree because it links two nodes that are already  in the tree.   A **minimum spanning tree** (MST) or minimum weight spanning tree  is a subset of the edges of a connected, edge-weighted  (un)directed graph that connects all the vertices together,  without any cycles and with the minimum possible total edge  weight. That is, it is a spanning tree whose sum of edge weights  is as small as possible. More generally, any edge-weighted  undirected graph (not necessarily connected) has a minimum  spanning forest, which is a union of the minimum spanning  trees for its connected components.   A planar graph and its minimum spanning tree. Each edge is  labeled with its weight, which here is roughly proportional  to its length.   This figure shows there may be more than one minimum spanning  tree in a graph. In the figure, the two trees below the graph  are two possibilities of minimum spanning tree of the given graph.   

prim

 A directed graph is called **strongly connected** if there is a path  in each direction between each pair of vertices of the graph.  In a directed graph G that may not itself be strongly connected,  a pair of vertices `u` and `v` are said to be strongly connected  to each other if there is a path in each direction between them.   Graph with strongly connected components marked   

strongly connected components

 In the field of computer science, a topological sort or  topological ordering of a directed graph is a linear ordering  of its vertices such that for every directed edge `uv` from  vertex `u` to vertex `v`, `u` comes before `v` in the ordering.  For instance, the vertices of the graph may represent tasks to  be performed, and the edges may represent constraints that one  task must be performed before another; in this application, a  topological ordering is just a valid sequence for the tasks.  A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph)  (DAG). Any DAG has at least one topological ordering, and algorithms are  known for constructing a topological ordering of any DAG in linear time.   A topological ordering of a directed acyclic graph: every edge goes from  earlier in the ordering (upper left) to later in the ordering (lower right).  A directed graph is acyclic if and only if it has a topological ordering.    The graph shown above has many valid topological sorts, including:    The canonical application of topological sorting is in  **scheduling a sequence of jobs** or tasks based on their dependencies. The jobs  are represented by vertices, and there is an edge from `x` to `y` if  job `x` must be completed before job `y` can be started (for  example, when washing clothes, the washing machine must finish  before we put the clothes in the dryer). Then, a topological sort  gives an order in which to perform the jobs.  Other application is **dependency resolution**. Each vertex is a package and each edge is a dependency of package `a` on package 'b'. Then topological sorting will provide a sequence of installing dependencies in a way that every next dependency has its dependent packages to be installed in prior.   

topological sorting

 The travelling salesman problem (TSP) asks the following question:  "Given a list of cities and the distances between each pair of  cities, what is the shortest possible route that visits each city  and returns to the origin city?"   Solution of a travelling salesman problem: the black line shows  the shortest possible loop that connects every red dot.   TSP can be modelled as an undirected weighted graph, such that  cities are the graph's vertices, paths are the graph's edges,  and a path's distance is the edge's weight. It is a minimization  problem starting and finishing at a specified vertex after having  visited each other vertex exactly once. Often, the model is a  complete graph (i.e. each pair of vertices is connected by an  edge). If no path exists between two cities, adding an arbitrarily  long edge will complete the graph without affecting the optimal tour.   

travelling salesman

 The task is to traverse the given linked list in reversed order.  For example for the following linked list:    The order of traversal should be:  37 → 99 → 12  The time complexity is `O(n)` because we visit every node only once.   

reverse traversal

  The task is to traverse the given linked list in straight order.  For example for the following linked list:   The order of traversal should be:  12 → 99 → 37  The time complexity is `O(n)` because we visit every node only once.   

traversal

This method shifts the relevant bit to the zeroth position. Then we perform `AND` operation with one which has bit pattern like `0001`. This clears all bits from the original number except the relevant one. If the relevant bit is one, the result is `1`, otherwise the result is `0`. > See [getBit.js](getBit.js) for further details. This method shifts `1` over by `bitPosition` bits, creating a value that looks like `00100`. Then we perform `OR` operation that sets specific bit into `1` but it does not affect on other bits of the number. > See [setBit.js](setBit.js) for further details. This method shifts `1` over by `bitPosition` bits, creating a value that looks like `00100`. Than it inverts this mask to get the number that looks like `11011`. Then `AND` operation is being applied to both the number and the mask. That operation unsets the bit. > See [clearBit.js](clearBit.js) for further details. This method is a combination of "Clear Bit" and "Set Bit" methods. > See [updateBit.js](updateBit.js) for further details. This method determines if the number provided is even. It is based on the fact that odd numbers have their last right bit to be set to 1. Number: 5 = 0b0101 isEven: false Number: 4 = 0b0100 isEven: true > See [isEven.js](isEven.js) for further details. This method determines if the number is positive. It is based on the fact that all positive numbers have their leftmost bit to be set to `0`. However, if the number provided is zero or negative zero, it should still return `false`. Number: 1 = 0b0001 isPositive: true Number: -1 = -0b0001 isPositive: false > See [isPositive.js](isPositive.js) for further details. This method shifts original number by one bit to the left. Thus all binary number components (powers of two) are being multiplying by two and thus the number itself is being multiplied by two. Before the shift Number: 0b0101 = 5 Powers of two: 0 + 2^2 + 0 + 2^0 After the shift Number: 0b1010 = 10 Powers of two: 2^3 + 0 + 2^1 + 0 > See [multiplyByTwo.js](multiplyByTwo.js) for further details. This method shifts original number by one bit to the right. Thus all binary number components (powers of two) are being divided by two and thus the number itself is being divided by two without remainder. Before the shift Number: 0b0101 = 5 Powers of two: 0 + 2^2 + 0 + 2^0 After the shift Number: 0b0010 = 2 Powers of two: 0 + 0 + 2^1 + 0 > See [divideByTwo.js](divideByTwo.js) for further details. This method make positive numbers to be negative and backwards. To do so it uses "Twos Complement" approach which does it by inverting all of the bits of the number and adding 1 to it. 1101 -3 1110 -2 1111 -1 0000 0 0001 1 0010 2 0011 3 > See [switchSign.js](switchSign.js) for further details. This method multiplies two signed integer numbers using bitwise operators. This method is based on the following facts: a * b can be written in the below formats: 0 if a is zero or b is zero or both a and b are zeroes 2a * (b/2) if b is even 2a * (b - 1)/2 + a if b is odd and positive 2a * (b + 1)/2 - a if b is odd and negative The advantage of this approach is that in each recursive step one of the operands reduces to half its original value. Hence, the run time complexity is `O(log(b))` where `b` is the operand that reduces to half on each recursive step. > See [multiply.js](multiply.js) for further details. This method multiplies two integer numbers using bitwise operators. This method is based on that "Every number can be denoted as the sum of powers of 2". The main idea of bitwise multiplication is that every number may be split to the sum of powers of two: I.e. 19 = 2^4 + 2^1 + 2^0 Then multiplying number `x` by `19` is equivalent of: x * 19 = x * 2^4 + x * 2^1 + x * 2^0 Now we need to remember that `x * 2^4` is equivalent of shifting `x` left by `4` bits (`x << 4`). > See [multiplyUnsigned.js](multiplyUnsigned.js) for further details. This method counts the number of set bits in a number using bitwise operators. The main idea is that we shift the number right by one bit at a time and check the result of `&` operation that is `1` if bit is set and `0` otherwise. Number: 5 = 0b0101 Count of set bits = 2 > See [countSetBits.js](countSetBits.js) for further details. This methods outputs the number of bits required to convert one number to another. This makes use of property that when numbers are `XOR`-ed the result will be number of different bits. 5 = 0b0101 1 = 0b0001 Count of Bits to be Flipped: 1 > See [bitsDiff.js](bitsDiff.js) for further details. To calculate the number of valuable bits we need to shift `1` one bit left each time and see if shifted number is bigger than the input number. 5 = 0b0101 Count of valuable bits is: 3 When we shift 1 four times it will become bigger than 5. > See [bitLength.js](bitLength.js) for further details. This method checks if a number provided is power of two. It uses the following property. Let's say that `powerNumber` is a number that has been formed as a power of two (i.e. 2, 4, 8, 16 etc.). Then if we'll do `&` operation between `powerNumber` and `powerNumber - 1` it will return `0` (in case if number is power of two). Number: 4 = 0b0100 Number: 3 = (4 - 1) = 0b0011 4 & 3 = 0b0100 & 0b0011 = 0b0000 <-- Equal to zero, is power of two. Number: 10 = 0b01010 Number: 9 = (10 - 1) = 0b01001 10 & 9 = 0b01010 & 0b01001 = 0b01000 <-- Not equal to zero, not a power of two. > See [isPowerOfTwo.js](isPowerOfTwo.js) for further details. This method adds up two integer numbers using bitwise operators. It implements [full adder](<https://en.wikipedia.org/wiki/Adder_(electronics)>) electronics circuit logic to sum two 32-bit integers in two's complement format. It's using the boolean logic to cover all possible cases of adding two input bits: with and without a "carry bit" from adding the previous less-significant stage. Legend: A = 3: 011 B = 6: 110 ┌──────┬────┬────┬─────────┬──────────┬─────────┬───────────┬───────────┐ │ bit │ ai │ bi │ carryIn │ carryOut │ bitSum │ resultBin │ resultDec │ ├──────┼────┼────┼─────────┼──────────┼─────────┼───────────┼───────────┤ │ 0 │ 1 │ 0 │ 0 │ 0 │ 1 │ 1 │ 1 │ │ 1 │ 1 │ 1 │ 0 │ 1 │ 0 │ 01 │ 1 │ │ 2 │ 0 │ 1 │ 1 │ 1 │ 0 │ 001 │ 1 │ │ 3 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1001 │ 9 │ └──────┴────┴────┴─────────┴──────────┴─────────┴───────────┴───────────┘ > See [fullAdder.js](fullAdder.js) for further details. > See [Full Adder on YouTube](https://www.youtube.com/watch?v=wvJc9CZcvBc&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8).

bits

  A **complex number** is a number that can be expressed in the form `a + b * i`, where `a` and `b` are real numbers, and `i` is a solution of the equation `x^2 = −1`. Because no _real number_ satisfies this equation, `i` is called an _imaginary number_. For the complex number `a + b * i`, `a` is called the _real part_, and `b` is called the _imaginary part_.   A Complex Number is a combination of a Real Number and an Imaginary Number:   Geometrically, complex numbers extend the concept of the one-dimensional number line to the _two-dimensional complex plane_ by using the horizontal axis for the real part and the vertical axis for the imaginary part. The complex number `a + b * i` can be identified with the point `(a, b)` in the complex plane.  A complex number whose real part is zero is said to be _purely imaginary_; the points for these numbers lie on the vertical axis of the complex plane. A complex number whose imaginary part is zero can be viewed as a _real number_; its point lies on the horizontal axis of the complex plane.   A complex number can be visually represented as a pair of numbers `(a, b)` forming a vector on a diagram called an _Argand diagram_, representing the _complex plane_.   > Complex does not mean complicated. It means the two types of numbers, real and > imaginary, together form a complex, just like a building complex (buildings > joined together).   An alternative way of defining a point `P` in the complex plane, other than using the x- and y-coordinates, is to use the distance of the point from `O`, the point whose coordinates are `(0, 0)` (the origin), together with the angle subtended between the positive real axis and the line segment `OP` in a counterclockwise direction. This idea leads to the polar form of complex numbers.   The _absolute value_ (or modulus or magnitude) of a complex number `z = x + yi` is:   The argument of `z` (in many applications referred to as the "phase") is the angle of the radius `OP` with the positive real axis, and is written as `arg(z)`. As with the modulus, the argument can be found from the rectangular form `x+yi`:   Together, `r` and `φ` give another way of representing complex numbers, the polar form, as the combination of modulus and argument fully specify the position of a point on the plane. Recovering the original rectangular co-ordinates from the polar form is done by the formula called trigonometric form:   Using Euler's formula this can be written as:     To add two complex numbers we add each part separately:  (a + b * i) + (c + d * i) = (a + c) + (b + d) * i  **Example**  (3 + 5i) + (4 − 3i) = (3 + 4) + (5 − 3)i = 7 + 2i  On complex plane the adding operation will look like the following:    To subtract two complex numbers we subtract each part separately:  (a + b * i) - (c + d * i) = (a - c) + (b - d) * i  **Example**  (3 + 5i) - (4 − 3i) = (3 - 4) + (5 + 3)i = -1 + 8i   To multiply complex numbers each part of the first complex number gets multiplied by each part of the second complex number:  Just use "FOIL", which stands for "**F**irsts, **O**uters, **I**nners, **L**asts" ( see [Binomial Multiplication](ttps://www.mathsisfun.com/algebra/polynomials-multiplying.html) for more details):    In general it looks like this:  (a + bi)(c + di) = ac + adi + bci + bdi^2  But there is also a quicker way!  Use this rule:  (a + bi)(c + di) = (ac − bd) + (ad + bc)i  **Example**  (3 + 2i)(1 + 7i) = 3×1 + 3×7i + 2i×1+ 2i×7i = 3 + 21i + 2i + 14i^2 = 3 + 21i + 2i − 14   (because i^2 = −1) = −11 + 23i  (3 + 2i)(1 + 7i) = (3×1 − 2×7) + (3×7 + 2×1)i = −11 + 23i   We will need to know about conjugates in a minute!  A conjugate is where we change the sign in the middle like this:   A conjugate is often written with a bar over it:  5 − 3i   =   5 + 3i  On the complex plane the conjugate number will be mirrored against real axes.    The conjugate is used to help complex division.  The trick is to _multiply both top and bottom by the conjugate of the bottom_.  **Example**  2 + 3i 4 − 5i  Multiply top and bottom by the conjugate of `4 − 5i`:    (2 + 3i) * (4 + 5i)   8 + 10i + 12i + 15i^2 = ------------------- = ----------------------   (4 − 5i) * (4 + 5i)   16 + 20i − 20i − 25i^2  Now remember that `i^2 = −1`, so:    8 + 10i + 12i − 15    −7 + 22i   −7   22 = ------------------- = -------- = -- + -- * i   16 + 20i − 20i + 25      41      41   41   There is a faster way though.  In the previous example, what happened on the bottom was interesting:  (4 − 5i)(4 + 5i) = 16 + 20i − 20i − 25i  The middle terms `(20i − 20i)` cancel out! Also `i^2 = −1` so we end up with this:  (4 − 5i)(4 + 5i) = 4^2 + 5^2  Which is really quite a simple result. The general rule is:  (a + bi)(a − bi) = a^2 + b^2   

complex number

  In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder.  The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, `21` is the GCD of `252` and number `21` is also the GCD of `105` and `252 − 105 = 147`. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.  By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., `21 = 5 × 105 + (−2) × 252`. The fact that the GCD can always be expressed in this way is known as Bézout's identity.   Euclid's method for finding the greatest common divisor (GCD) of two starting lengths `BA` and `DC`, both defined to be multiples of a common "unit" length. The length `DC` being shorter, it is used to "measure" `BA`, but only once because remainder `EA` is less than `DC`. EA now measures (twice) the shorter length `DC`, with remainder `FC` shorter than `EA`. Then `FC` measures (three times) length `EA`. Because there is no remainder, the process ends with `FC` being the `GCD`. On the right Nicomachus' example with numbers `49` and `21` resulting in their GCD of `7` (derived from Heath 1908:300).   A `24-by-60` rectangle is covered with ten `12-by-12` square tiles, where `12` is the GCD of `24` and `60`. More generally, an `a-by-b` rectangle can be covered with square tiles of side-length `c` only if `c` is a common divisor of `a` and `b`.   Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions `a = 1071` and `b = 462`. Squares of size `462×462` are placed within it leaving a squares until a `21×147` rectangle is left, which in turn is tiled with `21×21` squares, leaving no uncovered area. The smallest square size, `21`, is the GCD of `1071` and `462`.   

euclidean algorithm

 In mathematics, the **Euclidean distance** between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore occasionally being called the Pythagorean distance.     The distance between any two points on the real line is the absolute value of the numerical difference of their coordinates      In three dimensions, for points given by their Cartesian coordinates, the distance is   Example: the distance between the two points `(8,2,6)` and `(3,5,7)`:   In general, for points given by Cartesian coordinates in `n`-dimensional Euclidean space, the distance is    

euclidean distance

  In mathematics, the factorial of a non-negative integer `n`, denoted by `n!`, is the product of all positive integers less than or equal to `n`. For example:  5! = 5 * 4 * 3 * 2 * 1 = 120    

factorial

  **The power of a number** says how many times to use the number in a multiplication.  It is written as a small number to the right and above the base number.    How to find `a` raised to the power `b`?  We multiply `a` to itself, `b` times. That is, `a^b = a * a * a * ... * a` (`b` occurrences of `a`).  This operation will take `O(n)` time since we need to do multiplication operation exactly `n` times.   Can we do better than naive algorithm does? Yes we may solve the task of powering in `O(log(n))` time.  The algorithm uses divide and conquer approach to compute power. Currently the algorithm work for two positive integers `X` and `Y`.  The idea behind the algorithm is based on the fact that:  For **even** `Y`:  X^Y = X^(Y/2) * X^(Y/2)  For **odd** `Y`:  X^Y = X^(Y//2) * X^(Y//2) * X where Y//2 is result of division of Y by 2 without reminder.  **For example**  2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2)  2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2)  Now, since on each step we need to compute the same `X^(Y/2)` power twice we may optimise it by saving it to some intermediate variable to avoid its duplicate calculation.  **Time Complexity**  Since each iteration we split the power by half then we will call function recursively `log(n)` times. This the time complexity of the algorithm is reduced to:  O(log(n))   

fast powering

  In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:   A tiling with squares whose side lengths are successive Fibonacci numbers   The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling;[4] this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13 and 21.    

fibonacci

The **Fourier Transform** (**FT**) decomposes a function of time (a signal) into the frequencies that make it up, in a way similar to how a musical chord can be expressed as the frequencies (or pitches) of its constituent notes. The **Discrete Fourier Transform** (**DFT**) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous (and periodic), and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle. The Discrete Fourier transform transforms a sequence of `N` complex numbers: {xn} = x0, x1, x2 ..., xN-1 into another sequence of complex numbers: {Xk} = X0, X1, X2 ..., XN-1 which is defined by: The **Discrete-Time Fourier Transform** (**DTFT**) is a form of Fourier analysis that is applicable to the uniformly-spaced samples of a continuous function. The term discrete-time refers to the fact that the transform operates on discrete data (samples) whose interval often has units of time. From only the samples, it produces a function of frequency that is a periodic summation of the continuous Fourier transform of the original continuous function. A **Fast Fourier Transform** (**FFT**) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. These components are single sinusoidal oscillations at distinct frequencies each with their own amplitude and phase. This transformation is illustrated in Diagram below. Over the time period measured in the diagram, the signal contains 3 distinct dominant frequencies. View of a signal in the time and frequency domain: An FFT algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IFFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from O(n2), which arises if one simply applies the definition of DFT, to O(n log n), where n is the data size. Here a discrete Fourier analysis of a sum of cosine waves at 10, 20, 30, 40, and 50 Hz: The Fourier Transform is one of deepest insights ever made. Unfortunately, the meaning is buried within dense equations: and Rather than jumping into the symbols, let's experience the key idea firsthand. Here's a plain-English metaphor: **Think With Circles, Not Just Sinusoids** The Fourier Transform is about circular paths (not 1-d sinusoids) and Euler's formula is a clever way to generate one: Must we use imaginary exponents to move in a circle? Nope. But it's convenient and compact. And sure, we can describe our path as coordinated motion in two dimensions (real and imaginary), but don't forget the big picture: we're just moving in a circle. **Discovering The Full Transform** The big insight: our signal is just a bunch of time spikes! If we merge the recipes for each time spike, we should get the recipe for the full signal. The Fourier Transform builds the recipe frequency-by-frequency: A few notes: Stuart Riffle has a great interpretation of the Fourier Transform: - [FT](https://en.wikipedia.org/wiki/Fourier_transform) - [DFT](https://www.wikiwand.com/en/Discrete_Fourier_transform) - [DTFT](https://en.wikipedia.org/wiki/Discrete-time_Fourier_transform) - [FFT](https://www.wikiwand.com/en/Fast_Fourier_transform)

fourier transform

 In mathematics, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. With this method, it is possible to evaluate a polynomial with only `n` additions and `n` multiplications. Hence, its storage requirements are `n` times the number of bits of `x`.  Horner's method can be based on the following identity:   This identity is called _Horner's rule_.  To solve the right part of the identity above, for a given `x`, we start by iterating through the polynomial from the inside out, accumulating each iteration result. After `n` iterations, with `n` being the order of the polynomial, the accumulated result gives us the polynomial evaluation.   **Using the polynomial:**  Now, **using the same scenario but with Horner's rule**, the polynomial can be re-written as `x * (x * (x * (4 * x + 2) + 3) + 1) + 3`, representing it as `[4, 2, 3, 1, 3]` it is possible to save the first iteration as `acc = arr[0] * (x=2) + arr[1]`, and then finish iterations for `acc *= (x=2) + arr[index]`. In the same scenario but using Horner's rule, a total of `10` operations would have happened, composed of only `4` additions and `4` multiplications.   

horner method

 In number theory and combinatorics, a partition of a positive  integer `n`, also called an **integer partition**, is a way of  writing `n` as a sum of positive integers.   Two sums that differ only in the order of their summands are  considered the same partition. For example, `4` can be partitioned  in five distinct ways:  4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1  The order-dependent composition `1 + 3` is the same partition as `3 + 1`, while the two distinct  compositions `1 + 2 + 1` and `1 + 1 + 2` represent the same  partition `2 + 1 + 1`.  Young diagrams associated to the partitions of the positive integers `1` through `8`. They are arranged so that images  under the reflection about the main diagonal of the square  are conjugate partitions.    

integer partition

 Given a positive integer, write a function to find if it is a power of two or not.  **Naive solution**  In naive solution we just keep dividing the number by two unless the number becomes `1` and every time we do so, we check that remainder after division is always `0`. Otherwise, the number can't be a power of two.  **Bitwise solution**  Powers of two in binary form always have just one bit set. The only exception is with a signed integer (e.g. an 8-bit signed integer with a value of -128 looks like: `10000000`)  1: 0001 2: 0010 4: 0100 8: 1000  So after checking that the number is greater than zero, we can use a bitwise hack to test that one and only one bit is set.  number & (number - 1)  For example for number `8` that operations will look like:    1000   ----   0111    1000 & 0111   ----   0000   

is power of two

 In arithmetic and number theory, the least common multiple,  lowest common multiple, or smallest common multiple of  two integers `a` and `b`, usually denoted by `LCM(a, b)`, is  the smallest positive integer that is divisible by  both `a` and `b`. Since division of integers by zero is  undefined, this definition has meaning only if `a` and `b` are  both different from zero. However, some authors define `lcm(a,0)` as `0` for all `a`, which is the result of taking the `lcm` to be the least upper bound in the lattice of divisibility.   What is the LCM of 4 and 6?  Multiples of `4` are:  4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...  and the multiples of `6` are:  6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...  Common multiples of `4` and `6` are simply the numbers  that are in both lists:  12, 24, 36, 48, 60, 72, ....  So, from this list of the first few common multiples of  the numbers `4` and `6`, their least common multiple is `12`.   The following formula reduces the problem of computing the  least common multiple to the problem of computing the greatest  common divisor (GCD), also known as the greatest common factor:  lcm(a, b) = |a * b| / gcd(a, b)   A Venn diagram showing the least common multiples of  combinations of `2`, `3`, `4`, `5` and `7` (`6` is skipped as  it is `2 × 3`, both of which are already represented).  For example, a card game which requires its cards to be  divided equally among up to `5` players requires at least `60` cards, the number at the intersection of the `2`, `3`, `4` and `5` sets, but not the `7` set.   

least common multiple

 Liu Hui remarked in his commentary to The Nine Chapters on the Mathematical Art, that the ratio of the circumference of an inscribed hexagon to the diameter of  the circle was `three`, hence `π` must be greater than three. He went on to provide  a detailed step-by-step description of an iterative algorithm to calculate `π` to  any required accuracy based on bisecting polygons; he calculated `π` to  between `3.141024` and `3.142708` with a 96-gon; he suggested that `3.14` was  a good enough approximation, and expressed `π` as `157/50`; he admitted that  this number was a bit small. Later he invented an ingenious quick method to  improve on it, and obtained `π ≈ 3.1416` with only a 96-gon, with an accuracy  comparable to that from a 1536-gon. His most important contribution in this  area was his simple iterative `π` algorithm.   Liu Hui argued:  > Multiply one side of a hexagon by the radius (of its  circumcircle), then multiply this by three, to yield the  area of a dodecagon; if we cut a hexagon into a  dodecagon, multiply its side by its radius, then again  multiply by six, we get the area of a 24-gon; the finer  we cut, the smaller the loss with respect to the area  of circle, thus with further cut after cut, the area of  the resulting polygon will coincide and become one with  the circle; there will be no loss   Liu Hui's method of calculating the area of a circle.  Further, Liu Hui proved that the area of a circle is half of its circumference  multiplied by its radius. He said:  > Between a polygon and a circle, there is excess radius. Multiply the excess  radius by a side of the polygon. The resulting area exceeds the boundary of  the circle  In the diagram `d = excess radius`. Multiplying `d` by one side results in  oblong `ABCD` which exceeds the boundary of the circle. If a side of the polygon  is small (i.e. there is a very large number of sides), then the excess radius  will be small, hence excess area will be small.  > Multiply the side of a polygon by its radius, and the area doubles;  hence multiply half the circumference by the radius to yield the area of circle.   The area within a circle is equal to the radius multiplied by half the  circumference, or `A = r x C/2 = r x r x π`.   Liu Hui began with an inscribed hexagon. Let `M` be the length of one side `AB` of  hexagon, `r` is the radius of circle.   Bisect `AB` with line `OPC`, `AC` becomes one side of dodecagon (12-gon), let  its length be `m`. Let the length of `PC` be `j` and the length of `OP` be `G`.  the [Gou Gu](https://en.wikipedia.org/wiki/Pythagorean_theorem) (Pythagorean theorem) theorem repetitively:          From here, there is now a technique to determine `m` from `M`, which gives the  side length for a polygon with twice the number of edges. Starting with a  hexagon, Liu Hui could determine the side length of a dodecagon using this  formula. Then continue repetitively to determine the side length of a  24-gon given the side length of a dodecagon. He could do this recursively as  many times as necessary. Knowing how to determine the area of these polygons,  Liu Hui could then approximate `π`.   

liu hui

In mathematics, a **matrix** (plural **matrices**) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns. For example, the dimension of the matrix below is `2 × 3` (read "two by three"), because there are two rows and three columns: An `m × n` matrix: the `m` rows are horizontal, and the `n` columns are vertical. Each element of a matrix is often denoted by a variable with two subscripts. For example, a2,1 represents the element at the second row and first column of the matrix To add two matrices: add the numbers in the matching positions: The two matrices must be the same size, i.e. the rows must match in size, and the columns must match in size. To subtract two matrices: subtract the numbers in the matching positions: We can multiply a matrix by a constant (the value 2 in this case): To multiply a matrix by another matrix we need to do the [dot product](https://www.mathsisfun.com/algebra/vectors-dot-product.html) of rows and columns. To work out the answer for the **1st row** and **1st column**: Here it is for the 1st row and 2nd column: If we'll do the same for the rest of the rows and columns we'll get the following resulting matrix: To "transpose" a matrix, swap the rows and columns. We put a "T" in the top right-hand corner to mean transpose:

matrix

 In mathematics, **Pascal's triangle** is a triangular array of  the [binomial coefficients](https://en.wikipedia.org/wiki/Binomial_coefficient).  The rows of Pascal's triangle are conventionally enumerated  starting with row `n = 0` at the top (the `0th` row). The  entries in each row are numbered from the left beginning  with `k = 0` and are usually staggered relative to the  numbers in the adjacent rows. The triangle may be constructed in the following manner: In row `0` (the topmost row), there  is a unique nonzero entry `1`. Each entry of each subsequent row is constructed by adding the number above and to the  left with the number above and to the right, treating blank  entries as `0`. For example, the initial number in the  first (or any other) row is `1` (the sum of `0` and `1`), whereas the numbers `1` and `3` in the third row are added  to produce the number `4` in the fourth row.    The entry in the `nth` row and `kth` column of Pascal's  triangle is denoted ![Formula](https://wikimedia.org/api/rest_v1/media/math/render/svg/206415d3742167e319b2e52c2ca7563b799abad7). For example, the unique nonzero entry in the topmost  row is ![Formula example](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7e35f86368d5978b46c07fd6dddca86bd6e635c).  With this notation, the construction of the previous  paragraph may be written as follows:   for any non-negative integer `n` and any  integer `k` between `0` and `n`, inclusive.    We know that `i`-th entry in a line number `lineNumber` is  Binomial Coefficient `C(lineNumber, i)` and all lines start  with value `1`. The idea is to  calculate `C(lineNumber, i)` using `C(lineNumber, i-1)`. It  can be calculated in `O(1)` time using the following:  C(lineNumber, i)   = lineNumber! / ((lineNumber - i)! * i!) C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)  We can derive following expression from above two expressions:  C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i  So `C(lineNumber, i)` can be calculated  from `C(lineNumber, i - 1)` in `O(1)` time.   

pascal triangle

 A **prime number** (or a **prime**) is a natural number greater than `1` that  cannot be formed by multiplying two smaller natural numbers. A natural number  greater than `1` that is not prime is called a composite number. For  example, `5` is prime because the only ways of writing it as a  product, `1 × 5` or `5 × 1`, involve `5` itself. However, `6` is  composite because it is the product of two numbers `(2 × 3)` that are  both smaller than `6`.    A **primality test** is an algorithm for determining whether an input  number is prime. Among other fields of mathematics, it is used  for cryptography. Unlike integer factorization, primality tests  do not generally give prime factors, only stating whether the  input number is prime or not. Factorization is thought to be  a computationally difficult problem, whereas primality testing  is comparatively easy (its running time is polynomial in the  size of the input).    

primality test

  **Prime number** is a whole number greater than `1` that **cannot** be made by multiplying other whole numbers. The first few prime numbers are: `2`, `3`, `5`, `7`, `11`, `13`, `17`, `19` and so on.  If we **can** make it by multiplying other whole numbers it is a **Composite Number**.    **Prime factors** are those [prime numbers](https://en.wikipedia.org/wiki/Prime_number) which multiply together to give the original number. For example `39` will have prime factors of `3` and `13` which are also prime numbers. Another example is `15` whose prime factors are `3` and `5`.     The approach is to keep on dividing the natural number `n` by indexes from `i = 2` to `i = n` (by prime indexes only). The value of `n` is being overridden by `(n / i)` on each iteration.  The time complexity till now is `O(n)` in the worst case scenario since the loop runs from index `i = 2` to `i = n`. This time complexity can be reduced from `O(n)` to `O(sqrt(n))`. The optimisation is achievable when loop runs from `i = 2` to `i = sqrt(n)`. Now, we go only till `O(sqrt(n))` because when `i` becomes greater than `sqrt(n)`, we have the confirmation that there is no index `i` left which can divide `n` completely other than `n` itself.   In 1917, a theorem was formulated by G.H Hardy and Srinivasa Ramanujan which states that the normal order of the number `ω(n)` of distinct prime factors of a number `n` is `log(log(n))`.  Roughly speaking, this means that most numbers have about this number of distinct prime factors.   

prime factors

 The **radian** (symbol **rad**) is the unit for measuring angles, and is the  standard unit of angular measure used in many areas of mathematics.  The length of an arc of a unit circle is numerically equal to the measurement  in radians of the angle that it subtends; one radian is just under `57.3` degrees.  An arc of a circle with the same length as the radius of that circle subtends an  angle of `1 radian`. The circumference subtends an angle of `2π radians`.   A complete revolution is 2π radians (shown here with a circle of radius one and  thus circumference `2π`).   **Conversions**     

radian

 The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to some limit `n`.  It is attributed to Eratosthenes of Cyrene, an ancient Greek mathematician.   1. Create a boolean array of `n + 1` positions (to represent the numbers `0` through `n`) 2. Set positions `0` and `1` to `false`, and the rest to `true` 3. Start at position `p = 2` (the first prime number) 4. Mark as `false` all the multiples of `p` (that is, positions `2 * p`, `3 * p`, `4 * p`... until you reach the end of the array) 5. Find the first position greater than `p` that is `true` in the array. If there is no such position, stop. Otherwise, let `p` equal this new number (which is the next prime), and repeat from step 4  When the algorithm terminates, the numbers remaining `true` in the array are all  the primes below `n`.  An improvement of this algorithm is, in step 4, start marking multiples  of `p` from `p * p`, and not from `2 * p`. The reason why this works is because,  at that point, smaller multiples of `p` will have already been marked `false`.     The algorithm has a complexity of `O(n log(log n))`.   

sieve of eratosthenes

 In numerical analysis, a branch of mathematics, there are several square root  algorithms or methods of computing the principal square root of a non-negative real  number. As, generally, the roots of a function cannot be computed exactly. The root-finding algorithms provide approximations to roots expressed as floating point numbers.  Finding ![](https://wikimedia.org/api/rest_v1/media/math/render/svg/bff86975b0e7944720b3e635c53c22c032a7a6f1) is the same as solving the equation ![](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf57722151ef19ba1ca918d702b95c335e21cad) for a positive `x`. Therefore, any general numerical root-finding algorithm can be used.  **Newton's method** (also known as the Newton–Raphson method), named after  method for finding successively better approximations to the roots of a real-valued function.  Let's start by explaining the general idea of Newton's method and then apply it to our particular case with finding a square root of the number.   The Newton–Raphson method in one variable is implemented as follows:  The method starts with a function `f` defined over the real numbers `x`, the function's derivative `f'`, and an  initial guess `x0` for a root of the function `f`. If the function satisfies the assumptions made in the derivation  of the formula and the initial guess is close, then a better approximation `x1` is:   Geometrically, `(x1, 0)` is the intersection of the `x`-axis and the tangent of  the graph of `f` at `(x0, f (x0))`.  The process is repeated as:   until a sufficiently accurate value is reached.    As it was mentioned above, finding ![](https://wikimedia.org/api/rest_v1/media/math/render/svg/bff86975b0e7944720b3e635c53c22c032a7a6f1) is the same as solving the equation ![](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf57722151ef19ba1ca918d702b95c335e21cad) for a positive `x`.  The derivative of the function `f(x)` in case of square root problem is `2x`.  After applying the Newton's formula (see above) we get the following equation for our algorithm iterations:  x := x - (x² - S) / (2x)  The `x² − S` above is how far away `x²` is from where it needs to be, and the  division by `2x` is the derivative of `x²`, to scale how much we adjust `x` by how  quickly `x²` is changing.   

square root

 The **k-Means algorithm** is an unsupervised Machine Learning algorithm. It's a clustering algorithm, which groups the sample data on the basis of similarity between dimensions of vectors.  In k-Means classification, the output is a set of classes assigned to each vector. Each cluster location is continuously optimized in order to get the accurate locations of each cluster such that they represent each group clearly.  The idea is to calculate the similarity between cluster location and data vectors, and reassign clusters based on it. [Euclidean distance](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-distance) is used mostly for this task.    The algorithm is as follows:  1. Check for errors like invalid/inconsistent data 2. Initialize the `k` cluster locations with initial/random `k` points 3. Calculate the distance of each data point from each cluster 4. Assign the cluster label of each data point equal to that of the cluster at its minimum distance 5. Calculate the centroid of each cluster based on the data points it contains 6. Repeat each of the above steps until the centroid locations are varying  Here is a visualization of k-Means clustering for better understanding:    The centroids are moving continuously in order to create better distinction between the different set of data points. As we can see, after a few iterations, the difference in centroids is quite low between iterations. For example between iterations `13` and `14` the difference is quite small because there the optimizer is tuning boundary cases.   

k means

 The **k-nearest neighbors algorithm (k-NN)** is a supervised Machine Learning algorithm. It's a classification algorithm, determining the class of a sample vector using a sample data.  In k-NN classification, the output is a class membership. An object is classified by a plurality vote of its neighbors, with the object being assigned to the class most common among its `k` nearest neighbors (`k` is a positive integer, typically small). If `k = 1`, then the object is simply assigned to the class of that single nearest neighbor.  The idea is to calculate the similarity between two data points on the basis of a distance metric. [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance) is used mostly for this task.    The algorithm is as follows:  1. Check for errors like invalid data/labels. 2. Calculate the euclidean distance of all the data points in training data with the classification point 3. Sort the distances of points along with their classes in ascending order 4. Take the initial `K` classes and find the mode to get the most similar class 5. Report the most similar class  Here is a visualization of k-NN classification for better understanding:    The test sample (green dot) should be classified either to blue squares or to red triangles. If `k = 3` (solid line circle) it is assigned to the red triangles because there are `2` triangles and only `1` square inside the inner circle. If `k = 5` (dashed line circle) it is assigned to the blue squares (`3` squares vs. `2` triangles inside the outer circle).  Another k-NN classification example:    Here, as we can see, the classification of unknown points will be judged by their proximity to other points.  It is important to note that `K` is preferred to have odd values in order to break ties. Usually `K` is taken as `3` or `5`.   

 In computer science, binary search, also known as half-interval  search, logarithmic search, or binary chop, is a search algorithm  that finds the position of a target value within a sorted  array. Binary search compares the target value to the middle  element of the array; if they are unequal, the half in which  the target cannot lie is eliminated and the search continues  on the remaining half until it is successful. If the search  ends with the remaining half being empty, the target is not  in the array.    **Time Complexity**: `O(log(n))` - since we split search area by two for every next iteration.   

binary search

 **Interpolation search** is an algorithm for searching for a key in an array that  has been ordered by numerical values assigned to the keys (key values).  For example we have a sorted array of `n` uniformly distributed values `arr[]`,  and we need to write a function to search for a particular element `x` in the array.  **Linear Search** finds the element in `O(n)` time, **Jump Search** takes `O(√ n)` time  and **Binary Search** take `O(Log n)` time.  The **Interpolation Search** is an improvement over Binary Search for instances,  where the values in a sorted array are _uniformly_ distributed. Binary Search  always goes to the middle element to check. On the other hand, interpolation  search may go to different locations according to the value of the key being  searched. For example, if the value of the key is closer to the last element,  interpolation search is likely to start search toward the end side.  To find the position to be searched, it uses following formula:  // The idea of formula is to return higher value of pos // when element to be searched is closer to arr[hi]. And // smaller value when closer to arr[lo] pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))  arr[] - Array where elements need to be searched x - Element to be searched lo - Starting index in arr[] hi - Ending index in arr[]   **Time complexity**: `O(log(log(n))`   

interpolation search

Like Binary Search, **Jump Search** (or **Block Search**) is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements. For example, suppose we have an array `arr[]` of size `n` and block (to be jumped) of size `m`. Then we search at the indexes `arr[0]`, `arr[m]`, `arr[2 * m]`, ..., `arr[k * m]` and so on. Once we find the interval `arr[k * m] < x < arr[(k+1) * m]`, we perform a linear search operation from the index `k * m` to find the element `x`. **What is the optimal block size to be skipped?** In the worst case, we have to do `n/m` jumps and if the last checked value is greater than the element to be searched for, we perform `m - 1` comparisons more for linear search. Therefore the total number of comparisons in the worst case will be `((n/m) + m - 1)`. The value of the function `((n/m) + m - 1)` will be minimum when `m = √n`. Therefore, the best step size is `m = √n`. **Time complexity**: `O(√n)` - because we do search by blocks of size `√n`.

jump search

In computer science, linear search or sequential search is a  method for finding a target value within a list. It sequentially  checks each element of the list for the target value until a  match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most `n`  comparisons, where `n` is the length of the list.     **Time Complexity**: `O(n)` - since in worst case we're checking each element exactly once.  

linear search

 In set theory a Cartesian product is a mathematical operation that returns a set  (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.   Cartesian product `AxB` of two sets `A={x,y,z}` and `B={1,2,3}`    

cartesian product

 Given a **set** of candidate numbers (`candidates`) **(without duplicates)** and  a target number (`target`), find all unique combinations in `candidates` where  the candidate numbers sums to `target`.  The **same** repeated number may be chosen from `candidates` unlimited number  of times.  **Note:**    Input: candidates = [2,3,6,7], target = 7,  A solution set is:   [7],   [2,2,3] ]  Input: candidates = [2,3,5], target = 8,  A solution set is:   [2,2,2,2],   [2,3,3],   [3,5] ]   Since the problem is to get all the possible results, not the best or the  number of result, thus we don’t need to consider DP (dynamic programming), backtracking approach using recursion is needed to handle it.  Here is an example of decision tree for the situation when `candidates = [2, 3]` and `target = 6`:                  0               /   \            +2      +3           /   \      \        +2       +3    +3       /  \     /  \     \     +2    ✘   ✘   ✘     ✓    /  \   ✓    ✘       

combination sum

 When the order doesn't matter, it is a **Combination**.  When the order **does** matter it is a **Permutation**.  **"My fruit salad is a combination of apples, grapes and bananas"** We don't care what order the fruits are in, they could also be  "bananas, grapes and apples" or "grapes, apples and bananas",  its the same fruit salad.   This is how lotteries work. The numbers are drawn one at a  time, and if we have the lucky numbers (no matter what order)  we win!  No Repetition: such as lottery numbers `(2,14,15,27,30,33)`  **Number of combinations**   where `n` is the number of things to choose from, and we choose `r` of them, no repetition, order doesn't matter.  It is often called "n choose r" (such as "16 choose 3"). And is also known as the Binomial Coefficient.   Repetition is Allowed: such as coins in your pocket `(5,5,5,10,10)`  Or let us say there are five flavours of ice cream:   We can have three scoops. How many variations will there be?  Let's use letters for the flavours: `{b, c, l, s, v}`.  Example selections include:   **Number of combinations**   Where `n` is the number of things to choose from, and we  choose `r` of them. Repetition allowed,  order doesn't matter.   Permutations cheat sheet   Combinations cheat sheet   Permutations/combinations algorithm ideas.    

combinations

 The Fisher–Yates shuffle is an algorithm for generating a random  permutation of a finite sequence—in plain terms, the algorithm  shuffles the sequence. The algorithm effectively puts all the  elements into a hat; it continually determines the next element  by randomly drawing an element from the hat until no elements  remain. The algorithm produces an unbiased permutation: every  permutation is equally likely. The modern version of the  algorithm is efficient: it takes time proportional to the  number of items being shuffled and shuffles them in place.   

fisher yates

 The knapsack problem or rucksack problem is a problem in  combinatorial optimization: Given a set of items, each with  a weight and a value, determine the number of each item to  include in a collection so that the total weight is less  than or equal to a given limit and the total value is as  large as possible.  It derives its name from the problem faced by someone who is  constrained by a fixed-size knapsack and must fill it with the  most valuable items.  Example of a one-dimensional (constraint) knapsack problem:  which boxes should be chosen to maximize the amount of money  while still keeping the overall weight under or equal to 15 kg?     The most common problem being solved is the **0/1 knapsack problem**,  which restricts the number `xi` of copies of each kind of item to zero or one.  Given a set of n items numbered from `1` up to `n`, each with a  weight `wi` and a value `vi`, along with a maximum weight  capacity `W`,  maximize ![0/1 knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/85620037d368d2136fb3361702df6a489416931b)  subject to ![0/1 knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd6e7c9bca4397980976ea6d19237500ce3b8176) and ![0/1 knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/07dda71da2a630762c7b21b51ea54f86f422f951)  Here `xi` represents the number of instances of item `i` to  include in the knapsack. Informally, the problem is to maximize  the sum of the values of the items in the knapsack so that the  sum of the weights is less than or equal to the knapsack's  capacity.   The **bounded knapsack problem (BKP)** removes the restriction  that there is only one of each item, but restricts the number  integer value `c`:  maximize ![bounded knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/85620037d368d2136fb3361702df6a489416931b)  subject to ![bounded knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd6e7c9bca4397980976ea6d19237500ce3b8176) and ![bounded knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c8c5ac4f8247b3b8e01e89de76a1df0ea969821)   The **unbounded knapsack problem (UKP)** places no upper bound  on the number of copies of each kind of item and can be  formulated as above except for that the only restriction  on `xi` is that it is a non-negative integer.  maximize ![unbounded knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/85620037d368d2136fb3361702df6a489416931b)  subject to ![unbounded knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd6e7c9bca4397980976ea6d19237500ce3b8176)  and ![unbounded knapsack](https://wikimedia.org/api/rest_v1/media/math/render/svg/90a99710f61d5dea19e49ae5b31164d2b56b07e3)   

knapsack problem

 The longest common subsequence (LCS) problem is the problem of finding  the longest subsequence common to all sequences in a set of sequences  (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy  consecutive positions within the original sequences.    The longest common subsequence problem is a classic computer science  problem, the basis of data comparison programs such as the diff utility,  and has applications in bioinformatics. It is also widely used by  revision control systems such as Git for reconciling multiple changes  made to a revision-controlled collection of files.     

longest common subsequence

 The longest increasing subsequence problem is to find a subsequence of a  given sequence in which the subsequence's elements are in sorted order,  lowest to highest, and in which the subsequence is as long as possible.  This subsequence is not necessarily contiguous, or unique.    The longest increasing subsequence problem is solvable in  time `O(n log n)`, where `n` denotes the length of the input sequence.  Dynamic programming approach has complexity `O(n * n)`.   In the first 16 terms of the binary Van der Corput sequence  0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15  a longest increasing subsequence is  0, 2, 6, 9, 11, 15.  This subsequence has length six;  the input sequence has no seven-member increasing subsequences.  The longest increasing subsequence in this example is not unique: for  instance,  0, 4, 6, 9, 11, 15 or 0, 2, 6, 9, 13, 15 or 0, 4, 6, 9, 13, 15  are other increasing subsequences of equal length in the same  input sequence.   

longest increasing subsequence

 The maximum subarray problem is the task of finding the contiguous  subarray within a one-dimensional array, `a[1...n]`, of numbers  which has the largest sum, where,     The list usually contains both positive and negative numbers along  with `0`. For example, for the array of  values `−2, 1, −3, 4, −1, 2, 1, −5, 4` the contiguous subarray  with the largest sum is `4, −1, 2, 1`, with sum `6`.   

maximum subarray

 When the order doesn't matter, it is a **Combination**.  When the order **does** matter it is a **Permutation**.  **"The combination to the safe is 472"**. We do care about the order. `724` won't work, nor will `247`.  It has to be exactly `4-7-2`.   A permutation, also called an “arrangement number” or “order”, is a rearrangement of  the elements of an ordered list `S` into a one-to-one correspondence with `S` itself.   Below are the permutations of string `ABC`.   Or for example the first three people in a running race: you can't be first and second.  **Number of combinations**  n * (n-1) * (n -2) * ... * 1 = n!   When repetition is allowed we have permutations with repetitions. For example the the lock below: it could be `333`.   **Number of combinations**  n * n * n ... (r times) = n^r   Permutations cheat sheet   Combinations cheat sheet   Permutations/combinations algorithm ideas.    

permutations

 Power set of a set `S` is the set of all of the subsets of `S`, including the empty set and `S` itself. Power set of set `S` is denoted as `P(S)`.   For example for `{x, y, z}`, the subsets are:  {   {}, // (also denoted empty set ∅ or the null set)   {x},   {y},   {z},   {x, y},   {x, z},   {y, z},   {x, y, z} }   Here is how we may illustrate the elements of the power set of the set `{x, y, z}` ordered with respect to  inclusion:   **Number of Subsets**  If `S` is a finite set with `|S| = n` elements, then the number of subsets  of `S` is `|P(S)| = 2^n`. This fact, which is the motivation for the  notation `2^S`, may be demonstrated simply as follows:  > First, order the elements of `S` in any manner. We write any subset of `S` in  the format `{γ1, γ2, ..., γn}` where `γi , 1 ≤ i ≤ n`, can take the value  of `0` or `1`. If `γi = 1`, the `i`-th element of `S` is in the subset; otherwise, the `i`-th element is not in the subset. Clearly the number of  distinct subsets that can be constructed this way is `2^n` as `γi ∈ {0, 1}`.    Each number in binary representation in a range from `0` to `2^n` does exactly  what we need: it shows by its bits (`0` or `1`) whether to include related  element from the set or not. For example, for the set `{1, 2, 3}` the binary  number of `0b010` would mean that we need to include only `2` to the current set.   > See [bwPowerSet.js](./bwPowerSet.js) file for bitwise solution.   In backtracking approach we're constantly trying to add next element of the set to the subset, memorizing it and then removing it and try the same with the next element.  > See [btPowerSet.js](./btPowerSet.js) file for backtracking solution.   * [Wikipedia](https://en.wikipedia.org/wiki/Power_set) * [Math is Fun](https://www.mathsisfun.com/sets/power-set.html) 

power set

 The shortest common supersequence (SCS) of two sequences `X` and `Y`  is the shortest sequence which has `X` and `Y` as subsequences.  In other words assume we're given two strings str1 and str2, find  the shortest string that has both str1 and str2 as subsequences.  This is a problem closely related to the longest common  subsequence problem.   Input:   str1 = "geek",  str2 = "eke" Output: "geeke"  Input:   str1 = "AGGTAB",  str2 = "GXTXAYB" Output:  "AGXGTXAYB"   

shortest common supersequence

  Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order (ascending or descending arrangement). The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.      

bubble sort

 In computer science, **counting sort** is an algorithm for sorting  a collection of objects according to keys that are small integers;  that is, it is an integer sorting algorithm. It operates by  counting the number of objects that have each distinct key value,  and using arithmetic on those counts to determine the positions  of each key value in the output sequence. Its running time is  linear in the number of items and the difference between the  maximum and minimum key values, so it is only suitable for direct  use in situations where the variation in keys is not significantly  greater than the number of items. However, it is often used as a  subroutine in another sorting algorithm, radix sort, that can  handle larger keys more efficiently.  Because counting sort uses key values as indexes into an array,  it is not a comparison sort, and the `Ω(n log n)` lower bound for  comparison sorting does not apply to it. Bucket sort may be used  for many of the same tasks as counting sort, with a similar time  analysis; however, compared to counting sort, bucket sort requires  linked lists, dynamic arrays or a large amount of preallocated  memory to hold the sets of items within each bucket, whereas  counting sort instead stores a single number (the count of items)  per bucket.  Counting sorting works best when the range of numbers for each array element is very small.   **Step I**  In first step we calculate the count of all the elements of the  input array `A`. Then Store the result in the count array `C`. The way we count is depicted below.   **Step II**  In second step we calculate how many elements exist in the input  array `A` which are less than or equals for the given index.    **Step III**  In this step we place the input array `A` element at sorted  position by taking help of constructed count array `C` ,i.e what  we constructed in step two. We used the result array `B` to store  the sorted elements. Here we handled the index of `B` start from zero.       

counting sort

 Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The  improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.       

heap sort

 Insertion sort is a simple sorting algorithm that builds  the final sorted array (or list) one item at a time.  It is much less efficient on large lists than more  advanced algorithms such as quicksort, heapsort, or merge  sort.       

insertion sort

 In computer science, merge sort (also commonly spelled  mergesort) is an efficient, general-purpose,  comparison-based sorting algorithm. Most implementations  produce a stable sort, which means that the implementation  preserves the input order of equal elements in the sorted  output. Mergesort is a divide and conquer algorithm that  was invented by John von Neumann in 1945.  An example of merge sort. First divide the list into  the smallest unit (1 element), then compare each  element with the adjacent list to sort and merge the  two adjacent lists. Finally all the elements are sorted  and merged.   A recursive merge sort algorithm used to sort an array of 7  integer values. These are the steps a human would take to  emulate merge sort (top-down).      

merge sort

 Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller  sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays  The steps are:  1. Pick an element, called a pivot, from the array. 2. Partitioning: reorder the array so that all elements with  values less than the pivot come before the pivot, while all  elements with values greater than the pivot come after it  (equal values can go either way). After this partitioning,  the pivot is in its final position. This is called the  partition operation. 3. Recursively apply the above steps to the sub-array of  elements with smaller values and separately to the  sub-array of elements with greater values.  Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.      

quick sort

 In computer science, **radix sort** is a non-comparative integer sorting  algorithm that sorts data with integer keys by grouping keys by the individual  digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters  (e.g., names or dates) and specially formatted floating point numbers, radix  sort is not limited to integers.  *Where does the name come from?*  In mathematical numeral systems, the *radix* or base is the number of unique digits, including the digit zero, used to represent numbers in a positional numeral system.  For example, a binary system (using numbers 0 and 1) has a radix of 2 and a decimal  system (using numbers 0 to 9) has a radix of 10.   The topic of the efficiency of radix sort compared to other sorting algorithms is  somewhat tricky and subject to quite a lot of misunderstandings. Whether radix  sort is equally efficient, less efficient or more efficient than the best  comparison-based algorithms depends on the details of the assumptions made.  Radix sort complexity is `O(wn)` for `n` keys which are integers of word size `w`.  Sometimes `w` is presented as a constant, which would make radix sort better  (for sufficiently large `n`) than the best comparison-based sorting algorithms,  which all perform `O(n log n)` comparisons to sort `n` keys. However, in  general `w` cannot be considered a constant: if all `n` keys are distinct,  then `w` has to be at least `log n` for a random-access machine to be able to  store them in memory, which gives at best a time complexity `O(n log n)`. That  would seem to make radix sort at most equally efficient as the best  comparison-based sorts (and worse if keys are much longer than `log n`).      

radix sort

 Selection sort is a sorting algorithm, specifically an  in-place comparison sort. It has O(n2) time complexity,  making it inefficient on large lists, and generally  performs worse than the similar insertion sort.  Selection sort is noted for its simplicity, and it has  performance advantages over more complicated algorithms  in certain situations, particularly where auxiliary  memory is limited.       

selection sort

 Shellsort, also known as Shell sort or Shell's method,  is an in-place comparison sort. It can be seen as either a  generalization of sorting by exchange (bubble sort) or sorting  by insertion (insertion sort). The method starts by sorting  pairs of elements far apart from each other, then progressively  reducing the gap between elements to be compared. Starting  with far apart elements, it can move some out-of-place  elements into position faster than a simple nearest neighbor  exchange    For our example and ease of understanding, we take the interval  of `4`. Make a virtual sub-list of all values located at the  interval of 4 positions. Here these values are    We compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this   Then, we take interval of 2 and this gap generates two sub-lists    We compare and swap the values, if required, in the original array. After this step, the array should look like this   > UPD: On the picture below there is a typo and result array is supposed to be `[14, 10, 27, 19, 35, 33, 42, 44]`.  Finally, we sort the rest of the array using interval of value 1.  Shell sort uses insertion sort to sort the array.      

shell sort

 the Hamming distance between two strings of equal length is the  number of positions at which the corresponding symbols are  different. In other words, it measures the minimum number of substitutions required to change one string into the other, or  the minimum number of errors that could have transformed one  string into the other. In a more general context, the Hamming  distance is one of several string metrics for measuring the  edit distance between two sequences.   The Hamming distance between:    

hamming distance

 The Knuth–Morris–Pratt string searching algorithm (or  KMP algorithm) searches for occurrences of a "word" `W`  within a main "text string" `T` by employing the  observation that when a mismatch occurs, the word itself  embodies sufficient information to determine where the  next match could begin, thus bypassing re-examination  of previously matched characters.     

knuth morris pratt

 The Levenshtein distance is a string metric for measuring the  difference between two sequences. Informally, the Levenshtein  distance between two words is the minimum number of  single-character edits (insertions, deletions or substitutions)  required to change one word into the other.   Mathematically, the Levenshtein distance between two strings where   where  is the indicator function equal to `0` when and equal to 1 otherwise, and is the distance between the first `i` characters of `a` and the first   Note that the first element in the minimum corresponds to  deletion (from `a` to `b`), the second to insertion and  the third to match or mismatch, depending on whether the  respective symbols are the same.   For example, the Levenshtein distance between `kitten` and  into the other, and there is no way to do it with fewer than  three edits:  1. **k**itten → **s**itten (substitution of "s" for "k") 2. sitt**e**n → sitt**i**n (substitution of "i" for "e") 3. sittin → sittin**g** (insertion of "g" at the end).   This has a wide range of applications, for instance, spell checkers, correction  systems for optical character recognition, fuzzy string searching, and software  to assist natural language translation based on translation memory.   Let’s take a simple example of finding minimum edit distance between  strings `ME` and `MY`. Intuitively you already know that minimum edit distance  here is `1` operation, which is replacing `E` with `Y`. But  let’s try to formalize it in a form of the algorithm in order to be able to  do more complex examples like transforming `Saturday` into `Sunday`.  To apply the mathematical formula mentioned above to `ME → MY` transformation  we need to know minimum edit distances of `ME → M`, `M → MY` and `M → M` transformations in prior. Then we will need to pick the minimum one and add _one_ operation to  transform last letters `E → Y`. So minimum edit distance of `ME → MY` transformation  is being calculated based on three previously possible transformations.  To explain this further let’s draw the following matrix:   transform `M` to an empty string. And it is by deleting `M`. This is why this number is red. to transform `ME` to an empty string. And it is by deleting `E` and `M`. to transform an empty string to `M`. And it is by inserting `M`. This is why this number is green. to transform an empty string to `MY`. And it is by inserting `Y` and  `M`. to transform `M` into `M`. to transform `ME` to `M`. And it is by deleting `E`.  This looks easy for such small matrix as ours (it is only `3x3`). But here you may find basic concepts that may be applied to calculate all those numbers for bigger matrices (let’s say a `9x7` matrix for `Saturday → Sunday` transformation).  According to the formula you only need three adjacent cells `(i-1:j)`, `(i-1:j-1)`, and `(i:j-1)` to calculate the number for current cell `(i:j)`. All we need to do is to find the  minimum of those three cells and then add `1` in case if we have different  letters in `i`'s row and `j`'s column.  You may clearly see the recursive nature of the problem.   Let's draw a decision graph for this problem.   You may see a number of overlapping sub-problems on the picture that are marked  with red. Also there is no way to reduce the number of operations and make it  less than a minimum of those three adjacent cells from the formula.   Also you may notice that each cell number in the matrix is being calculated  based on previous ones. Thus the tabulation technique (filling the cache in  bottom-up direction) is being applied here.  Applying this principle further we may solve more complicated cases like  with `Saturday → Sunday` transformation.    

levenshtein distance

 The longest common substring problem is to find the longest string  (or strings) that is a substring (or are substrings) of two or more  strings.   The longest common substring of the strings `ABABC`, `BABCA` and   ABABC   |||  BABCA   |||   ABCBA   

longest common substring

 In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm  is a string searching algorithm created by Richard M. Karp and  Michael O. Rabin (1987) that uses hashing to find any one of a set  of pattern strings in a text.    The Rabin–Karp algorithm seeks to speed up the testing of equality of  the pattern to the substrings in the text by using a hash function. A  hash function is a function which converts every string into a numeric  value, called its hash value; for example, we might  have `hash('hello') = 5`. The algorithm exploits the fact  that if two strings are equal, their hash values are also equal. Thus, string matching is reduced (almost) to computing the hash value of the search pattern and then looking for substrings of the input string with that hash value.  However, there are two problems with this approach. First, because there are so many different strings and so few hash values, some differing strings will have the same hash value. If the hash values match, the pattern and the substring may not match; consequently, the potential match of search pattern and the substring must be confirmed by comparing them; that comparison can take a long time for long substrings. Luckily, a good hash function on reasonable strings usually does not have many collisions, so the expected search time will be acceptable.   The key to the Rabin–Karp algorithm's performance is the efficient computation  of hash values of the successive substrings of the text. The **Rabin fingerprint** is a popular and effective rolling hash function.  The **polynomial hash function** described in this example is not a Rabin  fingerprint, but it works equally well. It treats every substring as a  number in some base, the base being usually a large prime.   For text of length `n` and `p` patterns of combined length `m`, its average  and best case running time is `O(n + m)` in space `O(p)`, but its  worst-case time is `O(n * m)`.    A practical application of the algorithm is detecting plagiarism.  Given source material, the algorithm can rapidly search through a paper  for instances of sentences from the source material, ignoring details  such as case and punctuation. Because of the abundance of the sought  strings, single-string searching algorithms are impractical.   

rabin karp

 Given an input string `s` and a pattern `p`, implement regular  expression matching with support for `.` and `*`.   The matching should cover the **entire** input string (not partial).  **Note**    **Example #1**  Input: s = 'aa' p = 'a'  Output: `false`  Explanation: `a` does not match the entire string `aa`.  **Example #2**  Input: s = 'aa' p = 'a*'  Output: `true`  Explanation: `*` means zero or more of the preceding element, `a`.  Therefore, by repeating `a` once, it becomes `aa`.  **Example #3**  Input:  s = 'ab' p = '.*'  Output: `true`  Explanation: `.*` means "zero or more (`*`) of any character (`.`)".  **Example #4**  Input:  s = 'aab' p = 'c*a*b'  Output: `true`  Explanation: `c` can be repeated 0 times, `a` can be repeated  1 time. Therefore it matches `aab`.   

regular expression matching

 The Z-algorithm finds occurrences of a "word" `W`  within a main "text string" `T` in linear time `O(|W| + |T|)`.  Given a string `S` of length `n`, the algorithm produces  an array, `Z` where `Z[i]` represents the longest substring  starting from `S[i]` which is also a prefix of `S`. Finding with a nonce character, say `$` followed by the text, `T`, helps with pattern matching, for if there is some index `i` such that `Z[i]` equals the pattern length, then the pattern must be present at that point.  While the `Z` array can be computed with two nested loops in `O(|W| * |T|)` time, the following strategy shows how to obtain it in linear time, based  on the idea that as we iterate over the letters in the string  (index `i` from `1` to `n - 1`), we maintain an interval `[L, R]` which is the interval with maximum `R` such that `1 ≤ L ≤ i ≤ R`  and `S[L...R]` is a prefix that is also a substring (if no such  interval exists, just let `L = R =  - 1`). For `i = 1`, we can  simply compute `L` and `R` by comparing `S[0...]` to `S[1...]`.  **Example of Z array**  Index            0   1   2   3   4   5   6   7   8   9  10  11  Text             a   a   b   c   a   a   b   x   a   a   a   z Z values         X   1   0   0   3   1   0   0   2   2   1   0   Other examples  str =  a a a a a a Z[] =  x 5 4 3 2 1  str =  a a b a a c d Z[] =  x 1 0 2 1 0 0  str =  a b a b a b a b Z[] =  x 0 6 0 4 0 2 0  **Example of Z box**      

z algorithm

 Breadth-first search (BFS) is an algorithm for traversing  or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes  referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.    BFS(root)   Pre: root is the node of the BST   Post: the nodes in the BST have been visited in breadth first order   q ← queue   while root = ø     yield root.value     if root.left = ø       q.enqueue(root.left)     end if     if root.right = ø       q.enqueue(root.right)     end if     if !q.isEmpty()       root ← q.dequeue()     else       root ← ø     end if   end while end BFS   

  Say you have an array prices for which the `i`-th element is the price of a given stock on day `i`.  Find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).  > Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).  **Example #1**  Input: [7, 1, 5, 3, 6, 4] Output: 7   **Example #2**  Input: [1, 2, 3, 4, 5] Output: 4   **Example #3**  Input: [7, 6, 4, 3, 1] Output: 0     We may try **all** combinations of buying and selling and find out the most profitable one by applying _divide and conquer approach_.  Let's say we have an array of prices `[7, 6, 4, 3, 1]` and we're on the _1st_ day of trading (at the very beginning of the array). At this point we may say that the overall maximum profit would be the _maximum_ of two following values:  1. _Option 1: Keep the money_ → profit would equal to the profit from buying/selling the rest of the stocks → `keepProfit = profit([6, 4, 3, 1])`. 2. _Option 2: Buy/sell at current price_ → profit in this case would equal to the profit from buying/selling the rest of the stocks plus (or minus, depending on whether we're selling or buying) the current stock price → `buySellProfit = -7 + profit([6, 4, 3, 1])`.  The overall profit would be equal to → `overalProfit = Max(keepProfit, buySellProfit)`.  As you can see the `profit([6, 4, 3, 1])` task is being solved in the same recursive manner.  > See the full code example in [dqBestTimeToBuySellStocks.js](dqBestTimeToBuySellStocks.js)   As you may see, every recursive call will produce _2_ more recursive branches. The depth of the recursion will be `n` (size of prices array) and thus, the time complexity will equal to `O(2^n)`.  As you may see, this is very inefficient. For example for just `20` prices the number of recursive calls will be somewhere close to `2M`!   If we avoid cloning the prices array between recursive function calls and will use the array pointer then additional space complexity will be proportional to the depth of the recursion: `O(n)`   If we plot the prices array (i.e. `[7, 1, 5, 3, 6, 4]`) we may notice that the points of interest are the consecutive valleys and peaks    So, if we will track the growing price and will sell the stocks immediately _before_ the price goes down we'll get the maximum profit (remember, we bought the stock in the valley at its low price).  > See the full code example in [peakvalleyBestTimeToBuySellStocks.js](peakvalleyBestTimeToBuySellStocks.js)   Since the algorithm requires only one pass through the prices array, the time complexity would equal `O(n)`.   Except of the prices array itself the algorithm consumes the constant amount of memory. Thus, additional space complexity is `O(1)`.   There is even simpler approach exists. Let's say we have the prices array which looks like this `[1, 7, 2, 3, 6, 7, 6, 7]`:    You may notice, that we don't even need to keep tracking of a constantly growing price. Instead, we may simply add the price difference for _all growing segments_ of the chart which eventually sums up to the highest possible profit,  > See the full code example in [accumulatorBestTimeToBuySellStocks.js](accumulatorBestTimeToBuySellStocks.js)   Since the algorithm requires only one pass through the prices array, the time complexity would equal `O(n)`.   Except of the prices array itself the algorithm consumes the constant amount of memory. Thus, additional space complexity is `O(1)`.   

best time to buy sell stocks

 The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower and sometimes pluralized) is a mathematical game or puzzle.  It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in  a neat stack in ascending order of size on one rod, the smallest  at the top, thus making a conical shape.  The objective of the puzzle is to move the entire stack to another  rod, obeying the following simple rules:  stacks and placing it on top of another stack or on an empty rod.   Animation of an iterative algorithm solving 6-disk problem  With `3` disks, the puzzle can be solved in `7` moves. The minimal  number of moves required to solve a Tower of Hanoi puzzle  is `2^n − 1`, where `n` is the number of disks.   

hanoi tower

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. **Example #1** Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. **Example #2** Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index. We call a position in the array a **"good index"** if starting at that position, we can reach the last index. Otherwise, that index is called a **"bad index"**. The problem then reduces to whether or not index 0 is a "good index". This is the inefficient solution where we try every single jump pattern that takes us from the first position to the last. We start from the first position and jump to every index that is reachable. We repeat the process until last index is reached. When stuck, backtrack. > See [backtrackingJumpGame.js](backtrackingJumpGame.js) file **Time complexity:**: `O(2^n)`. There are 2n (upper bound) ways of jumping from the first position to the last, where `n` is the length of array `nums`. **Auxiliary Space Complexity**: `O(n)`. Recursion requires additional memory for the stack frames. Top-down Dynamic Programming can be thought of as optimized backtracking. It relies on the observation that once we determine that a certain index is good / bad, this result will never change. This means that we can store the result and not need to recompute it every time. Therefore, for each position in the array, we remember whether the index is good or bad. Let's call this array memo and let its values be either one of: GOOD, BAD, UNKNOWN. This technique is called memoization. > See [dpTopDownJumpGame.js](dpTopDownJumpGame.js) file **Time complexity:**: `O(n^2)`. For every element in the array, say `i`, we are looking at the next `nums[i]` elements to its right aiming to find a GOOD index. `nums[i]` can be at most `n`, where `n` is the length of array `nums`. **Auxiliary Space Complexity**: `O(2 * n) = O(n)`. First `n` originates from recursion. Second `n` comes from the usage of the memo table. Top-down to bottom-up conversion is done by eliminating recursion. In practice, this achieves better performance as we no longer have the method stack overhead and might even benefit from some caching. More importantly, this step opens up possibilities for future optimization. The recursion is usually eliminated by trying to reverse the order of the steps from the top-down approach. The observation to make here is that we only ever jump to the right. This means that if we start from the right of the array, every time we will query a position to our right, that position has already be determined as being GOOD or BAD. This means we don't need to recurse anymore, as we will always hit the memo table. > See [dpBottomUpJumpGame.js](dpBottomUpJumpGame.js) file **Time complexity:**: `O(n^2)`. For every element in the array, say `i`, we are looking at the next `nums[i]` elements to its right aiming to find a GOOD index. `nums[i]` can be at most `n`, where `n` is the length of array `nums`. **Auxiliary Space Complexity**: `O(n)`. This comes from the usage of the memo table. Once we have our code in the bottom-up state, we can make one final, important observation. From a given position, when we try to see if we can jump to a GOOD position, we only ever use one - the first one. In other words, the left-most one. If we keep track of this left-most GOOD position as a separate variable, we can avoid searching for it in the array. Not only that, but we can stop using the array altogether. > See [greedyJumpGame.js](greedyJumpGame.js) file **Time complexity:**: `O(n)`. We are doing a single pass through the `nums` array, hence `n` steps, where `n` is the length of array `nums`. **Auxiliary Space Complexity**: `O(1)`. We are not using any extra memory.

jump game

 A **knight's tour** is a sequence of moves of a knight on a chessboard  such that the knight visits every square only once. If the knight  ends on a square that is one knight's move from the beginning  square (so that it could tour the board again immediately,  following the same path), the tour is **closed**, otherwise it  is **open**.  The **knight's tour problem** is the mathematical problem of  finding a knight's tour. Creating a program to find a knight's  tour is a common problem given to computer science students. Variations of the knight's tour problem involve chessboards of  different sizes than the usual `8×8`, as well as irregular  (non-rectangular) boards.  The knight's tour problem is an instance of the more  general **Hamiltonian path problem** in graph theory. The problem of finding  a closed knight's tour is similarly an instance of the Hamiltonian  cycle problem.   An open knight's tour of a chessboard.   An animation of an open knight's tour on a 5 by 5 board.   

knight tour

 The **eight queens puzzle** is the problem of placing eight chess queens  on an `8×8` chessboard so that no two queens threaten each other.  Thus, a solution requires that no two queens share the same row,  column, or diagonal. The eight queens puzzle is an example of the  more general *n queens problem* of placing n non-attacking queens  on an `n×n` chessboard, for which solutions exist for all natural  numbers `n` with the exception of `n=2` and `n=3`.  For example, following is a solution for 4 Queen problem.   The expected output is a binary matrix which has 1s for the blocks  where queens are placed. For example following is the output matrix  for above 4 queen solution.  { 0,  1,  0,  0} { 0,  0,  0,  1} { 1,  0,  0,  0} { 0,  0,  1,  0}   Generate all possible configurations of queens on board and print a  configuration that satisfies the given constraints.  while there are untried configurations {    generate the next configuration    if queens don't attack in this configuration then    {       print this configuration;    } }   The idea is to place queens one by one in different columns,  starting from the leftmost column. When we place a queen in a  column, we check for clashes with already placed queens. In  the current column, if we find a row for which there is no  clash, we mark this row and column as part of the solution.  If we do not find such a row due to clashes then we backtrack  and return false.  1) Start in the leftmost column 2) If all queens are placed     return true 3) Try all rows in the current column.  Do following for every tried row.     a) If the queen can be placed safely in this row then mark this [row,          column] as part of the solution and recursively check if placing           queen here leads to a solution.     b) If placing queen in [row, column] leads to a solution then return          true.     c) If placing queen doesn't lead to a solution then umark this [row,          column] (Backtrack) and go to step (a) to try other rows. 3) If all rows have been tried and nothing worked, return false to trigger      backtracking.   Bitwise algorithm basically approaches the problem like this:  can only be one queen in each row, one in each column, and at most one on each  diagonal. place a queen, then move to the second row, place a second queen, and so on until either a) we reach a valid solution or b) we reach a dead end (ie. we can't place a queen such that it is "safe" from the other queens). horizontal attacks, since no queen will ever be on the same row as another queen. certain square: 1) The square's column doesn't have any other queens on it, 2) the square's left diagonal doesn't have any other queens on it, and 3) the square's right diagonal doesn't have any other queens on it. give up on our current attempt and immediately test out the next possibility.  First let's talk about the recursive function. You'll notice that it accepts  3 parameters: `leftDiagonal`, `column`, and `rightDiagonal`. Each of these is  technically an integer, but the algorithm takes advantage of the fact that an  integer is represented by a sequence of bits. So, think of each of these  parameters as a sequence of `N` bits.  Each bit in each of the parameters represents whether the corresponding location on the current row is "available".  For example: already occupied by a queen. top-left-to-bottom-right diagonals that pass through columns 4 and 5 of that  row are already occupied by queens.  Below is a visual aid for `leftDiagonal`, `column`, and `rightDiagonal`.      - [Wikipedia](https://en.wikipedia.org/wiki/Eight_queens_puzzle)   - [Solution by Greg Trowbridge](http://gregtrowbridge.com/a-bitwise-solution-to-the-n-queens-problem-in-javascript/)    

n queens

 Given an array of non-negative integers representing terraces in an elevation map  where the width of each bar is `1`, compute how much water it is able to trap  after raining.    **Example #1**  Input: arr[] = [2, 0, 2] Output: 2 Structure is like below:   We can trap 2 units of water in the middle gap.  **Example #2**  Input: arr[] = [3, 0, 0, 2, 0, 4] Output: 10 Structure is like below:       |  We can trap "3*2 units" of water between 3 an 2, "1 unit" on top of bar 2 and "3 units" between 2  and 4. See below diagram also.  **Example #3**  Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 Structure is like below:         |     |   || |  Trap "1 unit" between first 1 and 2, "4 units" between first 2 and 3 and "1 unit" between second last 1 and last 2.   An element of array can store water if there are higher bars on left and right.  We can find amount of water to be stored in every element by finding the heights  of bars on left and right sides. The idea is to compute amount of water that can be stored in every element of array. For example, consider the array on top of bar 2 and "3 units" between 2 and 4. See below diagram also.   **Intuition**  For each element in the array, we find the maximum level of water it can trap  after the rain, which is equal to the minimum of maximum height of bars on both  the sides minus its own height.  **Steps**    - Initialize `max_left = 0`  and `max_right = 0`   - Iterate from the current element to the beginning of array updating: `max_left = max(max_left, height[j])`   - Iterate from the current element to the end of array updating: `max_right = max(max_right, height[j])`   - Add `min(max_left, max_right) − height[i]` to `answer`  **Complexity Analysis**  Time complexity: `O(n^2)`. For each element of array, we iterate the left and right parts.  Auxiliary space complexity: `O(1)` extra space.   **Intuition**  In brute force, we iterate over the left and right parts again and again just to  find the highest bar size up to that index. But, this could be stored. Voila,  dynamic programming.  So we may pre-compute highest bar on left and right of every bar in `O(n)` time. Then use these pre-computed values to find the amount of water in every array element.  The concept is illustrated as shown:   **Steps**    - Add `min(max_left[i], max_right[i]) − height[i]` to `answer`.  **Complexity Analysis**  Time complexity: `O(n)`. We store the maximum heights upto a point using 2  iterations of `O(n)` each. We finally update `answer` using the stored  values in `O(n)`.  Auxiliary space complexity: `O(n)` extra space. Additional space  for `left_max` and `right_max` arrays than in Approach 1.   

rain terraces

  There are `n` stairs, a person standing at the bottom wants to reach the top. The person can climb either `1` or `2` stairs at a time. _Count the number of ways, the person can reach the top._    This is an interesting problem because there are several ways of how it may be solved that illustrate different programming paradigms.    

recursive staircase

  You are given an `n x n` 2D matrix (representing an image).  Rotate the matrix by `90` degrees (clockwise).  **Note**  You have to rotate the image **in-place**, which means you  have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.   **Example #1**  Given input matrix:    [1, 2, 3],   [4, 5, 6],   [7, 8, 9], ]  Rotate the input matrix in-place such that it becomes:    [7, 4, 1],   [8, 5, 2],   [9, 6, 3], ]  **Example #2**  Given input matrix:    [5, 1, 9, 11],   [2, 4, 8, 10],   [13, 3, 6, 7],   [15, 14, 12, 16], ]  Rotate the input matrix in-place such that it becomes:    [15, 13, 2, 5],   [14, 3, 4, 1],   [12, 6, 8, 9],   [16, 7, 10, 11], ]   We would need to do two reflections of the matrix:    Or we also could Furthermore, you can reflect diagonally  top-left/bottom-right and reflect horizontally.  A common question is how do you even figure out what kind  of reflections to do? Simply rip a square piece of paper, write a random word on it so you know its rotation. Then, flip the square piece of paper around until you figure out how to come to the solution.   Here is an example of how first line may be rotated using diagonal top-right/bottom-left rotation along with horizontal rotation.  Let's say we have a string at the top of the matrix:  A B C • • • • • •  Let's do top-right/bottom-left diagonal reflection:  A B C / / • / • •    And now let's do horizontal reflection:  A → → B → → C → →  The string has been rotated to 90 degree:  • • A • • B • • C   

square matrix rotation

 A robot is located at the top-left corner of a `m x n` grid  (marked 'Start' in the diagram below).  The robot can only move either down or right at any point in  time. The robot is trying to reach the bottom-right corner  of the grid (marked 'Finish' in the diagram below).  How many possible unique paths are there?    **Example #1**  Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right  **Example #2**  Input: m = 7, n = 3 Output: 28    First thought that might came to mind is that we need to build a decision tree  where `D` means moving down and `R` means moving right. For example in case of boars `width = 3` and `height = 2` we will have the following decision tree:                  START                 /   \                D     R              /     /   \            R      D      R          /      /         \         R      R            D         END    END          END  We can see three unique branches here that is the answer to our problem.  **Time Complexity**: `O(2 ^ n)` - roughly in worst case with square board of size `n`.  **Auxiliary Space Complexity**: `O(m + n)` - since we need to store current path with positions.   Let's treat `BOARD[i][j]` as our sub-problem.  Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one.  BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]; // since we can only move down or right.  Base cases are:  BOARD[0][any] = 1; // only one way to reach any top slot. BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column.  For the board `3 x 2` our dynamic programming matrix will look like:   Each cell contains the number of unique paths to it. We need  the bottom right one with number `3`.  **Time Complexity**: `O(m * n)` - since we're going through each cell of the DP matrix.  **Auxiliary Space Complexity**: `O(m * n)` - since we need to have DP matrix.   This question is actually another form of Pascal Triangle.  The corner of this rectangle is at `m + n - 2` line, and  at `min(m, n) - 1` position of the Pascal's Triangle.   

Algorithms

interpolation search

jump search

linear search