manasa_and_stones.js

// source: https://www.hackerrank.com/challenges/manasa-and-stones/problem
// video: https://youtu.be/LbqoacVy7ok

function stones(n, a, b) {
    // Use a set of numbers and iterate over all possibilities for n stones
    let possValues = new Set([0])
    let i = 0
    while(i < n - 1){ // starting with 1 default "0" rock
        // Messy time complexity; each iteration processes more elements
        // 2^0 + 2^1 + 2^2...2^n
        // https://en.wikipedia.org/wiki/Geometric_progression
        // O((2^n - 1)/(2 - 1)) => O(2^n - 1)
        const nextValues = new Set 
        for(const val of possValues){
            const aVal = val + a
            nextValues.add(aVal)
            
            const bVal = val + b
            nextValues.add(bVal)
        }
        possValues = nextValues
        i++
    }
    const output = Array.from(possValues) // convert set into array for sorting
    // Annoying sorting - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
    // "...built upon converting the elements into strings..." !!!!
    output.sort((a,b)=>a-b)
    // Sorting takes up O(xlogx)
    // where x is the size of the set, which is at most 2^(n-1)
    // O(2^(n-1) * log(2^(n-1))
    return output
    // Total time complexity:
    // O(2^n - 1) + O(2^(n-1) * log(2^(n-1))) Drop constants
    // O(2^n) + O(2^n * log(2^n)) Consolidate
    // O(2^n + 2^n * log(2^n)) Keep most significant term
    // O(2^n * log(2^n))
}