UniLecs - Задача 85

task85.js

/** Для положительных k, за исключением 2, наименьшим числом n, 
 * является последний член арифметической прогрессии(АП), 
 * для которой k лежит в диаппазоне 
 * (предыдущая сумма прогрессии < k <= сумма прогрессии).
 * Исходя из условия задачи, что n >= 1 следует, что k >= 1.
 * Сложность алгоритма: O(n);
 */
 
const validateAgrument = (k) => {
  if (typeof k !== 'number') throw new Error('agument must be a number');
  if (k < 0) throw new Error('argumnet must be positive');
  return k
}

const findNumberBrootForce = (k) => {
  const progression = validateAgrument(k);
  if (k === 2) return 3;
  let n = 0;
  let sum = 0;
  while (sum < progression) {
    n++;
    sum += n;
  }
  return n;
}

/** Второй варинта решения задачи c использованием того же подхода,
 * но с помощью метода наименьших квадратов.
 * Приравнивняв АП к k получим:
 * АП = n(n+1)/2 => n^2 + n - 2*АП = 0. Для n >= 1: n = (sqrt(1 + 8*АП) - 1) / 2
 * если округлить полученное выражение в большую сторону, получим искомое значение n.
 * Сложность алгоритма: ~O(1);
 */
const findNumberLeastSquare = (k) => {
  const number = validateAgrument(k);
  if (k === 2) return 3;
  const n = Math.ceil((Math.sqrt(8 * k - 1) - 1) / 2);
  return n
}

// Тест для брутфорса суммы

console.assert(findNumberBrootForce(2) === 3);
console.assert(findNumberBrootForce(1) === 1);
console.assert(findNumberBrootForce(12) === 5);
console.assert(findNumberBrootForce(35) === 8);
console.assert(findNumberLeastSquare(2558) === 72);
console.assert(findNumberBrootForce(1234567899876) === 1571348);
console.assert(findNumberLeastSquare(1234567899876) === 1571348);
console.time('findNumberBrootForce');
findNumberBrootForce(1234567899876)
console.timeEnd('findNumberBrootForce');
console.time('findNumberLeastSquare');
findNumberLeastSquare(123456789987654321123456789);
console.timeEnd('findNumberLeastSquare');