2

Задача на 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, однако, ничего не понял и стало очень интересно, как это реализовать. Если кто-то возьмется растолковать что к чему - буду безмерно благодарен за развернутый ответ с пояснениями. Заранее спасибо!

4
  • вы бы и условие задачи сюда перенесли бы, а то лениво бывает от ссылки к ссылке сказать
    – Zhihar
    Commented 2 февр. 2021 в 8:55
  • 1
    Применить немного математики. Пусть сумма 1+..+n = S. Тогда условие на выбранные числа записывается как S - a - b = a * b. Нехитрыми преобразованиями получаем выражение b = (S - a)/(a + 1). Итого можно бежать в цикле по a, вычислять b и проверять что оно целое и лежит в нужном диапазоне значений.
    – Alexey Ten
    Commented 2 февр. 2021 в 9:05
  • Ну и да, массив для этого совершенно не нужен
    – Alexey Ten
    Commented 2 февр. 2021 в 9:23
  • @AlexeyTen, оформите как ответ. я галочку поставлю. Спасибо большое. Вопрос можно закрыть. Commented 2 февр. 2021 в 9:58

1 ответ 1

2

Применить немного математики.

Обозначим сумму S = 1 + ... + n = n * (n + 1) / 2. Тогда условие на выбранные числа записывается как S - a - b = a * b. Нехитрыми преобразованиями получаем выражение b = (S - a)/(a + 1).

Итого можно бежать в цикле по a, вычислять b и проверять что оно целое и лежит в нужном диапазоне значений.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.