Как оптимальнее определить, сколько существует чисел с заданными количеством и суммой цифр?

Question

[Mark321]

Решаю задачу на codewars, тесты проходит, но по скорости не проходит, можно как-то оптимизировать?

const sumNum = (n) => {
  const arr = n.toString().split('').map(el => +el)
  return arr.reduce((acc,c) => acc+c, 0)
}

const isEqual = (n) => {
  n = n.toString().split('').map(el => +el)
  for(var i = 0; i < n.length; i++) {
   if(n[i] > n[i+1]) return false
 }
 return true
}

function findAll(n, k) {
  const res = []
  for(let i = 0; i < Number('1'+'0'.repeat(k)); i++) {
    if(i.toString().length === k) {
      const equal = isEqual(i)
      if(equal) {
        const val = sumNum(i)
        if(n === val && equal) res.push(i)
      }
    }
  }
  const maxVal = Math.max(...res)
  const minVal = Math.min(...res)
  if(res.length === 0) return []
  return [res.length, String(minVal), String(maxVal)]
}

Comments

[Stalker_RED]

А зачем вы постоянно конвертируете то в строку то обратно в число?

[WbICHA]

Если ты не заешь как решить самому, там всегда можно посмотреть ответы.

[Mark321]

WbICHA, жесть
мне просто интересно конкретно в чем моя ошибка, что мое решение такое долгое
и можно ли как-то конкретно мое решение сооптимизировать

[Stalker_RED]

Mark321, конечно можно оптимизировать.
Банальное вынесение вот этого чудо из цикла ускоряет код на порядки
Number('1'+'0'.repeat(k)).

А еще подсказка - не обязательно перебирать все числа.

[Mark321]

Stalker_RED, я уже в ответе поправил, я не с 0 бегу, сейчас еще подумаю как еще цифры исключить

Answer 1

[Rsa97]

function find(sum, n, m) {
  if (n === 1) {
    return [`${sum}`];
  }
  const result = [];
  const min = Math.max(m, Math.floor(sum - (n - 1) * 9));
  const max = Math.floor(sum / n);
  for (let i = min; i <= max; i += 1) {
    find(sum - i, n - 1, i).forEach((el) => result.push(`${i}${el}`));
  }
  return result;
}

function findAll(sum, n) {
  if (sum > n * 9 || sum < n) {
    return [];
  }
  const result = find(sum, n, 1);
  return [result.length, result[0], result.pop()];
}

На самом деле первый и последний элемент можно получить без формирования всех вариантов, но вот насчёт количества я не уверен.

Answer 2

[Alexandroppolus]

https://habr.com/ru/post/674838/comments/#comment_...

Comments

[Alexandroppolus]

это только количество вариантов. Минимум и максимум совсем тривиально

[Mark321]

ну как я понял из комментариев, то парень возвращал числа, поэтому они округлялись, я же возвращаю строки

[Alexandroppolus]

Mark321, это понятно. Просто у тебя цикл на 10^k итераций, что довольно медленно. Тут нельзя просто взять и решить влоб.

[Alexandroppolus]

Оформил свой вариант, тесты прошел, зачтено. До 1 kyu совсем немного )

Answer 3

[Mark321]

const isEqual = (n) => {
  n = n.toString().split('').map(el => +el)
  for(var i = 0; i < n.length; i++) {
   if(n[i] > n[i+1]) return false
 }
 return true
}

function findAll(n, k) {
  const res = []
  for(let i = Number('1'+'0'.repeat(k-1)); i < Number('1'+'0'.repeat(k)); i++) {
    const equal = isEqual(i)
    if(equal) {
      const val = i.toString().split('').map(el => +el).reduce((acc,c) => acc+c, 0)
      if(n === val && equal) res.push(i)
    }
  }
  if(res.length === 0) return []
  return [res.length, String(res[0]), String(res[res.length-1])]
}

вот так вроде лучше, но все равно не работает!