Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Max Product Finder with heap

task:
Max Product Finder
Create a maxProductFinderK() function that takes in a list of numbers and an integer k, and returns the largest product that can be attained from any k integers in the list. You may presume that the length of the list of integers is greater than or equal to k.

For example, maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 2) should return 72 and maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 3) should return 432.

I get on it 4/5 ): ,and i dont even know what is missing.
Code:

class MaxHeap {
    constructor() {
        this.heap = [];
    }
    get size() {
        return this.heap.length;
    }
    getParent(index) {
        return Math.floor((index - 1) / 2);
    }
    getLeft(index) {
        return 2 * index + 1;
    }
    getRight(index) {
        return 2 * index + 2;
    }
    add(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIndex = this.getParent(index);
            if (this.heap[parentIndex] < this.heap[index]) {
                [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
                index = parentIndex;
            } else {
                break;
            }
        }
    }
    remove() {
        if (this.heap.length === 0) {
            return null;
        }
        if (this.heap.length === 1) {
            return this.heap.pop();
        }
        let max = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);
        return max;
    }
    heapifyDown(index) {
        let left = this.getLeft(index);
        let right = this.getRight(index);
        let largest = index;
        if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
            largest = left;
        }
        if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
            largest = right;
        }
        if (largest !== index) {
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
            this.heapifyDown(largest);
        }
    }
    printHeap() {
        let arr = [];
        while (this.heap.length > 0) {
            let max = this.remove();
            arr.push(max);
        }
        return arr;
    }
}
function maxProductFinderK(numbers, size) {
  if(numbers.length === 0 || size === 0){
     return 0
  }
  if(size === numbers.length){
    return numbers.reduce((accumulator, currentValue) => accumulator * currentValue, 1);
  }
    let positive = new MaxHeap();
    let negative = new MaxHeap();
    for (let n of numbers) {
        if (n < 0) {
            negative.add(Math.abs(n));
        } else {
            positive.add(n);
        }
    }
    let k = size;
    positive = positive.printHeap();
    negative = negative.printHeap();

    console.log(positive);
    console.log(negative);



    let result = 1;
    while (negative.length >= 2 && positive.length >= 2 && k>=2) {
        let negativeProduct = negative[0] * negative[1]
        let positiveProduct = positive[0] * positive[1];
        if (negativeProduct > positiveProduct) {
            result *= negativeProduct;
            negative.shift();
            negative.shift();
        } else {
            result *= positiveProduct;
            positive.shift();
            positive.shift();
        }
        k -= 2;
    }

    while (positive.length >= 2 && k>=2) {
        result *= (positive[0] * positive[1]);
        positive.shift();
        positive.shift();
        k -= 2;
    }
    while (negative.length >= 2 && k>=2) {
        result *= (negative[0] * negative[1]);
        negative.shift();
        negative.shift();
        k -= 2;
    }

    // console.log(k)

    if (k === 1) {
        if (positive.length > 0) {
            result *= positive[0];
        } else {
            result *= negative[0];
        }
    }
    console.log("result is "+ result);
    return result
}
Tags:

2

Answers


  1. 0

    You could simply sort the array and check the first two values as product against the last two items as product and take the ones with the larger product. Finally if only one item k is left take the largest value (at end of sorted array).

    function maxProductFinderK(values, k) {
    let product = 1;
    values.sort((a, b) => a - b);
    while (k) {
        if (k === 1) {
            const value = values.at(-1);
            if (value < 0) return; // or throw error
            product *= value;
            break;
        }
        const fn = values[0] * values[1] > values.at(-1) * values.at(-2)
            ? 'shift'
            : 'pop';
        product *= values[fn]() * values[fn]();
        k -= 2;
    }
    return product;
}

console.log(maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 2)); //  72
console.log(maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 3)); // 432
    Login or Signup to reply.
  2. 0

    Use the spread operator ... to create a copy of the values array, ensuring that the original array remains unchanged then sort it in ascending order. Use slice(-k) to extract the last k elements from the sorted array.
    Finally, we use reduce to calculate the product of these k largest elements.

     function maxProductFinderK(values, k) {
    const sortedValues = [...values].sort((a, b) => a - b);

    return sortedValues.slice(-k).reduce((acc, curr) => acc * curr, 1);
}

console.log(maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 2)); // 72
console.log(maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 3)); // 432
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search