JS: Algorithm Questions

In [ ]:

    

var isPrime = n => {
    if (n < 2 || !Number.isInteger(n)) {
        return false
    }
    for (let i = 2; i < Math.sqrt(n); i++){
        if (n % i == 0) {
            return false
        }
    }
    return true
}


    

In [ ]:

    

var isPrime = n => {
    if (n < 2 || !Number.isInteger(n)) {
        return false
    }
    if (n > 2 && n % 2 == 0){
        return false
    }
    let i = 3
    for (let i = 3; i < Math.sqrt(n); i += 2){
        if (n % i == 0) {
            return false
        }
    }
    return true
}


    

In [ ]:

    

for (const n of [...Array(100).keys()]) {
    if (isPrime(n)) {
        process.stdout.write(`${n}, `)
    }
}


    

In [ ]:

    

var primeFactors = n => {
    let factors = []
    if (n < 1 || !Number.isInteger(n)) {
        return factors
    }
    let divisor = 2
    while (n > 2) {
        if (n % divisor == 0) {
            factors.push(divisor)
            n = n / divisor
        }
        else n += 1
    }
    return factors
}


    

In [ ]:

    

primeFactors(60)


    

In [ ]:

    

// O(n), looping
var fibo = n => {
    if (n < 1 || !Number.isInteger(n)) return 0
    let [a, b] = [0, 1]
    for (const i of [...Array(n).keys()]) [a, b] = [b, a+b]
    return a
}


    

In [ ]:

    

// O(n), looping
Number.prototype.times = function(callback) {
    for (let i = 0; i < this.valueOf(); i++) callback(i)
}
var fibo = n => {
    if (n < 1 || !Number.isInteger(n)) return 0
    let [a, b] = [0, 1]
    n.times(() => {[a, b] = [b, a+b]})
    return a
}


    

In [ ]:

    

// O(n^2), recursive
var fibo = n => {
    if (n < 1 || !Number.isInteger(n)) return 0
    // if ([1, 2].includes(n)) return 1
    if (n === 1) return 1
    return fib(n - 1) + fib(n - 2)
}


    

In [ ]:

    

// O(n), recursive, with hashmap
var fibo = n => {
    const fiboMap = new Map()
        .set(0, 0)
        .set(1, 1)
    const fibonacci = n => {
        if (n < 1 || !Number.isInteger(n)) return 0
        return fiboMap.get(n) || fibonacci(n - 1) + fib(n - 2)
    }
    return fibonacci(n)
}


    

In [ ]:

    

for (const n of [...Array(20).keys()]) {
    process.stdout.write(`${fibo(n)}, `)
}


    

In [ ]:

    

// iterative Euclidean
var gcd = (a, b) => {
    let [x, y] = [a, b]
    while (y > 0) [x, y] = [y, x % y]
    return x
}


    

In [ ]:

    

// recursive Euclidean
var gcd = (a, b) => (b === 0)? a : gcd(b, a % b)


    

In [ ]:

    

// iterative Binary GCD
// from https://en.wikipedia.org/wiki/Binary_GCD_algorithm
var gcd = (u, v) =>{
    let shift = 0
    // if one is zero, return the other
    if (u == 0) return v
    if (v == 0) return u
    // if both even, divide by 2 and note it
    while (!((u | v) & 1)) {
        u >>= 1
        v >>= 1
        shift ++
    }
    // if only one is even, devide it by 2
    while (!(u & 1)) u >>= 1
    while (v != 0) {
        /* remove all factors of 2 in v -- they are not common */
        while (!(v & 1)) v >>= 1
        /* Now u and v are both odd. Swap if necessary so u <= v,
        then set v = v - u (which is even). For bignums, the
        swapping is just pointer movement, and the subtraction
        can be done in-place. */
        if (u > v) [u, v] = [v, u] // Swap u and v.
        v = v - u; // Here v >= u.
    }
    /* restore common factors of 2 */
    return u << shift
}


    

In [ ]:

    

// recursive Binary GCD
// from https://en.wikipedia.org/wiki/Binary_GCD_algorithm
var gcd = (u, v) =>
{
    // simple cases (termination)
    if (u == v) return u;

    if (u == 0) return v;

    if (v == 0) return u;

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

    if (~v & 1) return gcd(u, v >> 1);

    // reduce larger argument
    if (u > v) [u, v] = [v, u]
    return gcd((v - u) >> 1, u);
}


    

In [ ]:

    

gcd(12, 16)


    

In [ ]:

    

var noDup = arr => Array.from(new Set(arr))


    

In [ ]:

    

var noDup = arr => {
    const arrMap = new Map()
    arr.forEach(element => {
        if (!arrMap.get(element)) arrMap.set(element, true)
    })
    return Array.from(arrMap.keys())
}


    

In [ ]:

    

noDup([1, 1, 3, 7, 5, 5, 3, 2])


    

In [ ]:

    

var mergeArr = (a1, a2) => {
//     let [i, j] = [0, 0]
//     while (i < a1.length && j < a2.length) {
        
//     }
    const ret = []
    while (a1 && a2) {
        ret.push((a1[0] < a2[0]) ? a1.shift() : a2.shift())
    }
    return ret
}


    

In [ ]:

    

mergeArr([2,5,6,9], [1,2,3,29])


    

In [1]:

    

var swap = (a, b) => {
    b -= a
    a += b
    b = a - b
    return [a, b]
}


    

In [2]:

    

var swap = (a, b) => {
    a ^= b
    b ^= a
    a ^= b
    return [a, b]
}


    

In [ ]: