Ежедневная проблема кодирования № 2:

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.
For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Решение грубой силы

Решение грубой силы является наиболее интуитивным подходом. Обычно нужно понять, как работает человеческий разум, и превратить это в код.

Как работает наш мозг: мы пройдемся по массиву и для каждого слота/индекса умножим значения, которых нет в слоте i, и поместим продукт в новый множество. Продолжаем, пока не достигнем конца массива.

const calculateProduct = (array) => {
    for (let i = 0; i < array.length; i++) {
        let product = 1;
        for (let j = 0; j < array.length; j++) {
            if (j !== i) {
                const currentValue = array[j];
                product = product * currentValue;
            }
        }
        results[i] = product;
    }
    return results;
};

Мы будем перебирать массив в for loop. Мы инициализируем переменную product значением 1.

Затем у нас будет второй for loop, который также начинается с 0, но будет проверка, чтобы убедиться, что мы умножаем значение только при i !== j. После прохода по массиву для индекса i мы устанавливаем продукт в массиве results. В конце мы возвращаем массив results.

Решение O(n)

Учитывая, что это проблема кодирования, должен быть гораздо лучший подход, чем решение грубой силы O (n²). И есть!

Что мы можем сделать, так это найти общее произведение всех значений в массиве, пройдя по массиву один раз, что равно O (n). Затем мы повторяем второй раз, который также равен O(n), но на этот раз мы разделим произведение на значение в текущем индексе i и поместим результат в массив results. Общая временная сложность составляет O(2n) или просто O(n).

const calculateProduct = (array) => {
    const results = [];
    let product = 1;
    for (let i = 0; i < array.length; i++) {
        const currentValue = array[i];
        product = product * currentValue;
    }
    for (let j = 0; j < array.length; j++) {
        const currentValue = array[j];
        const result = product / currentValue;
        results.push(result);
    }
    return results;
};

O(n) без деления

Чтобы найти решение без использования деления, мы должны использовать дополнительное пространство для этого компромисса. У нас будет два дополнительных массива для вычисления накопительного произведения слева и справа от индекса.

const calculateProduct = (array) => {
    const left = [];
    const right = [];
    const results = [];
    for (let i = 0; i < array.length; i++) {
        left[i] = (left[i - 1] * array[i - 1]) || 1;
    }
    for (let j = array.length - 1; j >= 0; j--) {
        right[j] = (right[j + 1] * array[j + 1] || 1);
    }
    for (let k = 0; k < array.length; k++) {
        results[k] = left[k] * right[k];
    }
    return results;
};

Решения в моем REPL: https://repl.it/@etea13/Product-in-an-Array