Задача на codewars: https://www.codewars.com/kata/5547cc7dcad755e480000004
function removeNb(n) {
let arr = new Array(n)
let result = []
while (n > 0) {
arr[n - 1] = n
n--
}
for (let flag = 1; flag < arr.length; flag++) {
arr.splice(flag - 1, 1)
arr.forEach((cursor) => {
let temp = arr.slice(cursor, arr.length)
let difference = arr.filter((x) => !temp.includes(x))
difference.splice(difference.indexOf(cursor), 1)
temp = difference.concat(temp)
temp = temp.reduce((sum, el) => (sum += el))
if (flag * cursor === temp) {
result.push([flag, cursor])
}
})
arr.splice(flag - 1, 0, flag)
}
return result
}
let result = removeNb(26)
console.log(result)
code {white-space: nowrap !important;}
Решение написал, но из-за цикла в цикле на больших числах превышаю лимит по времени выполнения, как можно оптимизировать данную функцию? Как избежать цикла в цикле? Где-то что-то читал про n log n, однако, ничего не понял и стало очень интересно, как это реализовать. Если кто-то возьмется растолковать что к чему - буду безмерно благодарен за развернутый ответ с пояснениями. Заранее спасибо!
1+..+n = S
. Тогда условие на выбранные числа записывается какS - a - b = a * b
. Нехитрыми преобразованиями получаем выражениеb = (S - a)/(a + 1)
. Итого можно бежать в цикле поa
, вычислятьb
и проверять что оно целое и лежит в нужном диапазоне значений.