Idea: use bitwise AND operator to check if the least significant bit (right-most bit) is 1. This means the number is odd.
if (n & 1) // n is odd
For example, 13 = 1101 is represented as the sum of powers of two multiplied by the corresponding ones or zeros:
1101 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 8 + 4 + 0 + 1 = 13.
The bottom line is that 2 to any degree, except 0, is an even number. The sum of even numbers is an even number. From this we conclude that only the least significant bit affects parity.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Idea: loop from 2 until our number n minus 1 because n will be divisible by itself and 1. If the remainder of n with the current loop value i is 0 then it is not prime.
for (var i = 2; i < n; i++) {
if (n % i == 0) return false;
return n > 1;
}
Better idea: trial division method - if we don't find a divisor of n after checking up to square root of n, then n must be prime. If n is divisible by some number x, then n = x * y and if y were smaller than x, n would have been detected earlier as being divisible by y or by a prime factor of y.
n = x * y
x <= y
x * x <= x * y
x^2 <= n
x <= sqrt(n)
for (var i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0) return false;
return n > 1;
}
Sieve of Eratosthenes - simple, ancient algorithm for finding all prime numbers up to a given limit.
Idea: iteratively mark as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.
function allPrimes(n) {
var primes = [];
var result = [];
for (var i = 2; i < n; i++) {
primes[i] = true;
}
var limit = Math.sqrt(n);
for (var i = 2; i < limit; i++) {
if (primes[i] === true) {
for (var j = i * i; j < n; j += i) {
primes[j] = false;
}
}
}
for (var i = 2; i < n; i++) {
if (primes[i] === true) {
result.push(i);
}
}
return result;
}
Idea: 2^0 = 1
2^3 = 1*2*2*2 = 8
2^-3 = 1/2/2/2 = 0.125
function power(base, exp) {
var result = 1;
if (exp > 0) {
while(exp--) result *= base;
} else {
while(exp++) result /= base;
}
return result;
}
Idea: 5! = 5*4*3*2*1 = 120; 0! = 1
Recursive:
function fact(n) {
if (n > 0) return n * fact(n - 1);
else if (n == 0) return 1;
else return;
}
Non-recursive:
function factNonRecur(n) {
if (n > 0) {
var result = n;
while (n-- > 2) result *= n;
return result;
}
else if (n == 0) return 1;
else return;
}
Task: find n-th number in Fibonacci sequence.
Idea: f = 1, 1, 2, 3, 5, 8...; f_n = f_n-1 + f_n-2
Recursive:
function fib(n) {
if (n > 1) {
return fib(n - 1) + fib(n - 2);
}
else if (n == 1) return 1;
else if (n == 0) return 0;
else return;
}
Non-recursive:
function fibNonRecur(n) {
var result = 1, current = 1, prev = 0;
var temp;
while (current < n) {
temp = result;
result += prev;
prev = temp;
current++;
}
return result;
}
Better:
function fibBetter(n) {
var a = 1, b = 1, c;
for (var i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
Task: find first n numbers of Fibonacci sequence.
function fibSeq(n) {
var fibArr = [];
if (n < 3) {
for (var i = 0; i < n; i++) {
fibArr[i] = 1;
}
} else {
for (var i = 0; i < 2; i++) {
fibArr[i] = 1;
}
for (var i = 2; i < n; i++) {
fibArr[i] = fibArr[i-1] + fibArr[i-2];
}
}
return fibArr;
}
Better:
function fibSeqBetter(n) {
var fibArr = [];
for (var i = 0; i < n; i++) {
fibArr.push((i < 2) ? 1 : fibArr[i-1] + fibArr[i-2]);
}
return fibArr;
}
Linear:
var arr = [100, 10, -5, 2, 13, 0, 1];
var x = 2; // value to search in arr
function searchLinear(arr, x) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] === x) return i; // found at position i
}
return -1; // not found
}
Optimized, using barrier:
function searchLinearOpt(arr, x) {
var i = 0;
arr.push(x); // using barrier
while (arr[i] !== x) i++;
return (i == arr.length-1) ? -1 : i;
}
Binary:
var arr = [100, 10, 3, 12, -50, 18, 4];
var x = 3; // number to search in arr
// working with sorted array
arrSorted = arr.sort(function(a, b) { return a - b; });
// arrSorted = [-50, 1, 2, 5, 10, 18, 100]
function binarySearch(arr, x) {
var l = 0; // left border
var r = arr.length; // right border
var m; // middle position
while (l < r) {
m = Math.floor((l + r) / 2);
if (arr[m] < x) l = m + 1;
else r = m;
}
return (l == r && arr[l] != x) ? -1 : l;
}
Simple:
var str = "Hoola-Hoola girls like Hooligans.";
var pat = "Hooligans"; // search pattern
function search(str, pat) {
var sl = str.length;
var pl = pat.length;
var i = 0; // index, runs through str chars
var j = 0; // index, runs through pat chars
while (true) {
if (i <= sl - pl && j < pl && str[i+j] === pat[j]) j++;
else if (i <= sl - pl && j < pl) { i++; j = 0; }
else break;
}
return (i > sl-pl) ? -1 : i;
}
Knuth–Morris–Pratt (KMP):
var str = "Hoola-Hoola girls like Hooligans.";
var pat = "ool"; // search pattern
// make a prefix table where table[i] will store
// the length of the longest prefix
// (which is also a suffix) of the pattern pat[0..i]
function makeTable(pat) {
var table = [0]; // array with element = 0
var p = 0; // prefix index
var s = 1; // suffix index
while (s < pat.length) {
if (pat[p] === pat[s]) {
table[s] = p + 1;
s++;
p++;
} else if (p === 0) {
table[s] = 0;
s++;
} else {
p = table[p - 1];
}
}
return table;
}
// search for a match and return all positions
// where 'pat' was found in 'str'
function searchKMP(str, pat) {
var matchesArr = []; // positions where mathes were found
var s = 0; // string 'str' index
var p = 0; // pattern 'pat' index
const table = makeTable(pat);
while (s < str.length) {
if (str[s] === pat[p]) { // match
if (p === pat.length - 1) {
matchesArr.push((s - pat.length) + 1);
}
p++;
s++;
} else if (p > 0) {
p = table[p - 1];
} else {
p = 0;
s++;
}
}
return (matchesArr) ? matchesArr : -1;
}
Boyer-Moore (BM):
var str = "Hoola-Hoola girls like Hooligans.";
var pat = "Hooligan";
function searchBM(str, pat) {
var position = 0; // position along str
var offset = str.length - pat.length;
var last = pat.length - 1;
var badMatchTable = [];
if (last < 0) return 0;
// Generate the bad match table, which is the location of offsets
// to jump forward when a comparison fails
for (var i = 0; i < last; i++) {
badMatchTable[pat[i]] = last - i;
}
// search for the pattern
while (position <= offset) {
// Search right-to-left checking if the current position at
// pat and str match. If they do, rewind 1, repeat, and if we
// eventually match the first character, return the position.
for (var i = last; pat[i] === str[i+position]; i--) {
if (i === 0) return position;
}
position += badMatchTable[str[position+last]] || last || 1;
}
return -1;
}
Selection sort: First find the smallest element in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.
function selectionSort(arr) {
// i < arr.length-1 because last element
// will be already sorted
for (var i = 0; i < arr.length - 1; i++) {
// assume first element is min
var minIndex = i;
// check elements after i to find the smallest
for (var j = i+1; j < arr.length; j++) {
// if element is less then min it is the new minimum
if (arr[j] < arr[minIndex]) minIndex = j;
}
// swap min element with the leftmost unsorted element
if (minIndex != i) {
var temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
Insertion sort: The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up if necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part.
function insertionSort(arr) {
var key, j;
// 1st element in unsorted part will be 1st element in sorted part
for (var i = 1; i < arr.length; i++) {
key = arr[i]; // element we are moving into the sorted part
j = i; // index in unsorted part
// iterate through sorted part from right to left;
// stop iterating when element to the left of current position
// is less than the element we are trying to insert
while (j > 0 && arr[j-1] > key) {
// shift each element one space to the right
arr[j] = arr[j-1];
j--; // update counter
}
arr[j] = key; // insert element into the sorted part
}
}
Heap sort: The basic idea is to turn the array into a heap (binary tree structure) with max element in the root. Then repeatedly remove the max element from the heap, building the sorted list from back to front.
function heapSort(arr) {
buildMaxHeap(arr); // build max heap
var last = arr.length - 1; // last element
// continue heap sorting until we have
// only one element left in the array
while (last > 0) {
swap(arr, 0, last); // put max in the end
heapify(arr, 0, last);
last--;
}
}
// build max heap
function buildMaxHeap(arr) {
var i = Math.floor(arr.length / 2 - 1);
while (i >= 0) {
heapify(arr, i, arr.length);
i--;
}
}
// move (sift) one element at a time
// down to its correct location in the heap
function heapify(heap, i, max) {
var parent, leftChild, rightChild;
while (i < max) {
parent = i; // index of parent
leftChild = 2*i + 1; // index of left child
rightChild = leftChild + 1; // index of right child
if (leftChild < max && heap[leftChild] > heap[parent]) {
parent = leftChild;
}
if (rightChild < max && heap[rightChild] > heap[parent]) {
parent = rightChild;
}
if (parent == i) return;
swap(heap, i, parent);
i = parent;
}
}
// swap elements
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Quick sort: It is a divide and conquer algorithm. 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. 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.
function quickSort(arr, left = 0, right = arr.length-1) {
var i = left;
var j = right;
var temp;
// reference element *
var pivot = arr[Math.floor(left + (right - left) / 2)];
do {
while (arr[i] < pivot) i++;
while (pivot < arr[j]) j--;
if (i <= j) {
// swap
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// increment
i++;
j--;
}
} while (i <= j);
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}
// * You shouldn't compute the middle point as (left+right)/2.
// If the array is very large, the result of "left+right" may overflow and become negative.
// The proper way of choosing the midpoint pivot is: "left + (right-left)/2"
// which is mathematically equivalent but immune to overflow.
Merge sort: It is a divide and conquer algorithm. 1. Divide a list into n sublists, each containing one element (a list of one element is considered sorted). 2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining.
function mergeSort(arr) {
if (arr.length < 2) return arr; // terminal case
var middle = Math.floor(arr.length / 2);
var left = arr.slice(0, middle); // left subarray
var right = arr.slice(middle); // right subarray
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
var iLeft = 0; // index in left subarray
var iRight = 0; // index in right subarray
while (iLeft < left.length && iRight < right.length) {
if (left[iLeft] < right[iRight]) {
result.push(left[iLeft]);
iLeft++;
} else {
result.push(right[iRight]);
iRight++;
}
}
// fill the leftovers
while (iLeft < left.length) {
result.push(left[iLeft]);
iLeft++;
}
while (iRight < right.length) {
result.push(right[iRight]);
iRight++;
}
return result;
// or instead of the last 2 while loops
// return result.concat(left.slice(iLeft)).concat(right.slice(iRight));
}