Сумма чисел в диапазоне

Решение: Сумма чисел в диапазоне

1. Наивное решение O(n)

function sumRangeNaive(start: number, end: number): number {
  let sum = 0;
  const min = Math.min(start, end);
  const max = Math.max(start, end);
  
  for (let i = min; i <= max; i++) {
    sum += i;
  }
  
  return sum;
}

console.log(sumRangeNaive(1, 5));   // 15
console.log(sumRangeNaive(5, 1));   // 15
console.log(sumRangeNaive(-3, 3));  // 0

Минусы: На диапазоне 1-1,000,000 требует 1M итераций

2. Оптимальное решение O(1) - Формула арифметической прогрессии

function sumRange(start: number, end: number): number {
  // Гарантируем, что start <= end
  const min = Math.min(start, end);
  const max = Math.max(start, end);
  
  // Формула: sum = n * (first + last) / 2
  // где n = количество элементов
  const count = max - min + 1;
  const sum = (count * (min + max)) / 2;
  
  return sum;
}

console.log(sumRange(1, 5));   // 15
console.log(sumRange(5, 1));   // 15
console.log(sumRange(-3, 3));  // 0
console.log(sumRange(10, 10)); // 10

3. Объяснение формулы

Пример: sumRange(1, 5)

Диапазон: 1, 2, 3, 4, 5
Сумма: 1 + 2 + 3 + 4 + 5 = ?

Парный метод (Гаусс):
  1 + 5 = 6
  2 + 4 = 6
  3    = 3
  ------
Итого: 3 пары по 6 + 3 = 6 + 6 + 3 = 15

Формула:
  n = 5 (количество элементов)
  first = 1, last = 5
  sum = n * (first + last) / 2
  sum = 5 * (1 + 5) / 2
  sum = 5 * 6 / 2
  sum = 30 / 2
  sum = 15 ✓

Пример: sumRange(-3, 3)

Диапазон: -3, -2, -1, 0, 1, 2, 3
Парный метод:
  (-3) + 3 = 0
  (-2) + 2 = 0
  (-1) + 1 = 0
  0       = 0
  -------
  Итого: 0

Формула:
  count = 3 - (-3) + 1 = 7
  sum = 7 * ((-3) + 3) / 2
  sum = 7 * 0 / 2
  sum = 0 ✓

4. Как работает диапазон

function sumRange(start: number, end: number): number {
  // Шаг 1: Определяем границы
  const min = Math.min(start, end);
  const max = Math.max(start, end);
  
  // Шаг 2: Считаем количество элементов
  // Если диапазон [min, max], то элементов = max - min + 1
  // Примеры:
  // [1, 5]: 5 - 1 + 1 = 5 элементов (1, 2, 3, 4, 5) ✓
  // [5, 5]: 5 - 5 + 1 = 1 элемент (5) ✓
  // [10, 15]: 15 - 10 + 1 = 6 элементов (10, 11, 12, 13, 14, 15) ✓
  const count = max - min + 1;
  
  // Шаг 3: Применяем формулу
  // sum = количество_элементов * (первый + последний) / 2
  const sum = (count * (min + max)) / 2;
  
  return sum;
}

5. Варианты с рекурсией

// Простая рекурсия O(n)
function sumRangeRecursive(start: number, end: number): number {
  if (start === end) {
    return start;
  }
  
  if (start > end) {
    return 0;
  }
  
  return start + sumRangeRecursive(start + 1, end);
}

// Мемоизация: кэширует результаты
const memo = new Map<string, number>();

function sumRangeMemo(start: number, end: number): number {
  const key = `${start}-${end}`;
  
  if (memo.has(key)) {
    return memo.get(key)!;
  }
  
  if (start === end) {
    return start;
  }
  
  const result = start + sumRangeMemo(start + 1, end);
  memo.set(key, result);
  return result;
}

6. Производительность

const large = 1_000_000;

console.time('Naive O(n)');
sumRangeNaive(1, large);
console.timeEnd('Naive O(n)'); // ~10ms

console.time('Formula O(1)');
sumRange(1, large);
console.timeEnd('Formula O(1)'); // <0.1ms

// На диапазоне 1 - 1,000,000:
// Сумма = 1,000,000 * 1,000,001 / 2 = 500,000,500,000

7. Математическая формула подробнее

Сумма арифметической прогрессии:

S = n * (a₁ + aₙ) / 2

где:
  S  = сумма
  n  = количество членов
  a₁ = первый член
  aₙ = последний член

Почему это работает: Если у нас есть последовательность: a₁, a₂, ..., aₙ То: S = a₁ + a₂ + ... + aₙ И: S = aₙ + aₙ₋₁ + ... + a₁

Складываем два выражения: 2S = (a₁ + aₙ) + (a₂ + aₙ₋₁) + ... Каждая скобка = (a₁ + aₙ), таких скобок n штук 2S = n * (a₁ + aₙ)

S = n * (a₁ + aₙ) / 2

8. Edge cases

console.log(sumRange(5, 1));      // 15 (обратный диапазон)
console.log(sumRange(10, 10));    // 10 (один элемент)
console.log(sumRange(-5, -1));    // -15 (отрицательные)
console.log(sumRange(-2, 2));     // 0 (симметричные)
console.log(sumRange(0, 0));      // 0
console.log(sumRange(-1000, 1000)); // 0

9. Альтернативная реализация (без Math.min/max)

function sumRange(start: number, end: number): number {
  // Гарантируем start <= end
  if (start > end) {
    [start, end] = [end, start]; // Swap
  }
  
  const count = end - start + 1;
  return (count * (start + end)) / 2;
}

10. Тестирование

test('sumRange базовые случаи', () => {
  expect(sumRange(1, 5)).toBe(15);   // 1+2+3+4+5
  expect(sumRange(5, 1)).toBe(15);   // обратный
  expect(sumRange(-3, 3)).toBe(0);   // симметричный
  expect(sumRange(10, 10)).toBe(10); // один элемент
});

test('sumRange отрицательные диапазоны', () => {
  expect(sumRange(-5, -1)).toBe(-15); // -5-4-3-2-1
  expect(sumRange(-2, 2)).toBe(0);    // -2-1+0+1+2
});

test('sumRange большие диапазоны', () => {
  // Сумма 1 до 1000
  expect(sumRange(1, 1000)).toBe(500500);
});

Выводы

• Наивное: O(n) время, O(1) память — медленно на больших диапазонах
• Формула: O(1) время, O(1) память — идеально! ✓
• Ключ: Знание математических формул критично для оптимизации
• Нужно уметь переходить от итеративного решения к математическому