Сумма чётных чисел

Сумма чётных чисел

Задача: Вычислить сумму всех чётных чисел от 1 до N, желательно за O(1).

Решение 1: Наивный подход (цикл)

Проходим по всем чётным числам и суммируем:

def sum_even(n: int) -> int:
    """
    Сумма чётных чисел от 1 до N — простой цикл.
    """
    total = 0
    for i in range(2, n + 1, 2):
        total += i
    return total

# Тестирование
test_cases = [
    (10, 30),   # 2 + 4 + 6 + 8 + 10 = 30
    (7, 12),    # 2 + 4 + 6 = 12
    (1, 0),     # Нет чётных чисел
    (2, 2),     # Только 2
    (5, 6),     # 2 + 4 = 6
    (100, 2550),  # Большое число
]

for n, expected in test_cases:
    result = sum_even(n)
    status = "✓" if result == expected else "✗"
    print(f"{status} sum_even({n}) = {result}")

Сложность:

• Время: O(n) — проходим по всем чётным числам
• Память: O(1) — используем только одну переменную

Решение 2: С использованием sum() и range()

Используем встроенные функции Python:

def sum_even(n: int) -> int:
    """
    Сумма чётных чисел — с использованием sum() и range().
    """
    return sum(range(2, n + 1, 2))

# Тестирование
for n, expected in test_cases:
    result = sum_even(n)
    status = "✓" if result == expected else "✗"
    print(f"{status} sum_even({n}) = {result}")

Сложность:

• Время: O(n) — все равно проходим по n/2 элементам
• Память: O(1) — range() в Python 3 — это итератор, не список

Решение 3: Математическая формула (O(1))

Вместо итерации, используем математику. Чётные числа образуют арифметическую последовательность:

2, 4, 6, 8, ..., 2k

Где k = floor(n / 2) — количество чётных чисел от 1 до n.

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

S = (количество членов) × (первый член + последний член) / 2
S = k × (2 + 2k) / 2
S = k × (1 + k)
S = k + k²

Где k = n // 2

def sum_even(n: int) -> int:
    """
    Сумма чётных чисел — O(1) формула.
    
    Арифметическая последовательность: 2, 4, 6, ..., 2k
    Где k = n // 2
    
    Формула: S = k * (k + 1)
    """
    k = n // 2  # Количество чётных чисел
    return k * (k + 1)  # k + k²

# Тестирование
for n, expected in test_cases:
    result = sum_even(n)
    status = "✓" if result == expected else "✗"
    print(f"{status} sum_even({n}) = {result}")

Как это работает:

Для n = 10:
  k = 10 // 2 = 5
  Чётные числа: 2, 4, 6, 8, 10 (всего 5 чисел)
  
  Сумма = k * (k + 1) = 5 * 6 = 30 ✓
  Проверка: 2 + 4 + 6 + 8 + 10 = 30 ✓

Для n = 7:
  k = 7 // 2 = 3
  Чётные числа: 2, 4, 6 (всего 3 числа)
  
  Сумма = 3 * 4 = 12 ✓
  Проверка: 2 + 4 + 6 = 12 ✓

Для n = 100:
  k = 100 // 2 = 50
  Чётные числа: 2, 4, 6, ..., 100 (всего 50 чисел)
  
  Сумма = 50 * 51 = 2550 ✓

Сложность:

• Время: O(1) — только две операции (деление и умножение)
• Память: O(1) — только две переменные

Вывод формулы

Докажем формулу:

Сумма = 2 + 4 + 6 + 8 + ... + 2k

Выносим 2:
Сумма = 2 * (1 + 2 + 3 + ... + k)

Формула суммы первых k чисел: 1 + 2 + ... + k = k(k+1)/2

Сумма = 2 * k(k+1)/2 = k(k+1)

Так что формула S = k(k+1), где k = n // 2

Решение 4: Альтернативная запись

Можно также использовать формулу:

def sum_even(n: int) -> int:
    """
    Альтернативная формула: S = n/2 * (n/2 + 1)
    """
    return (n // 2) * ((n // 2) + 1)

# Или более лаконично:
def sum_even_short(n: int) -> int:
    """Краткая запись."""
    m = n >> 1  # Побитовый сдвиг (деление на 2)
    return m * (m + 1)

# Тестирование
for n, expected in test_cases:
    result = sum_even_short(n)
    status = "✓" if result == expected else "✗"
    print(f"{status} sum_even({n}) = {result}")

Сравнение производительности

import timeit

n = 10**9  # Очень большое число
iterations = 100000

# Решение 1: цикл (на больших числах будет очень медленно)
# time1 = timeit.timeit(lambda: sum_even_loop(n), number=iterations)
# print(f"Цикл: {time1:.4f}s")

# Решение 2: sum() и range()
# time2 = timeit.timeit(lambda: sum_even_sum(n), number=iterations)
# print(f"sum(): {time2:.4f}s")

# Решение 3: Формула O(1)
time3 = timeit.timeit(lambda: sum_even(n), number=iterations)
print(f"Формула O(1): {time3:.4f}s")

print()
print(f"Результат для n = {n}: {sum_even(n)}")

Математическое обоснование

Арифметическая последовательность:

• Первый член: a₁ = 2
• Последний член: aₖ = 2k (где k = n // 2)
• Количество членов: k
• Разность: d = 2

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

S = (количество членов) × (первый + последний) / 2
S = k × (2 + 2k) / 2
S = k × (1 + k)
S = k + k²

Граничные случаи

def test_edge_cases():
    # n < 2: нет чётных чисел
    assert sum_even(0) == 0
    assert sum_even(1) == 0
    
    # n = 2: только одно чётное число
    assert sum_even(2) == 2
    
    # Нечётные n
    assert sum_even(1) == 0
    assert sum_even(3) == 2  # 2
    assert sum_even(5) == 6  # 2 + 4
    assert sum_even(7) == 12  # 2 + 4 + 6
    
    # Чётные n
    assert sum_even(2) == 2
    assert sum_even(4) == 6  # 2 + 4
    assert sum_even(6) == 12  # 2 + 4 + 6
    assert sum_even(10) == 30  # 2 + 4 + 6 + 8 + 10
    
    # Большие числа
    assert sum_even(1000) == 500 * 501  # 250500
    assert sum_even(1000000) == 500000 * 500001
    
    print("Все тесты пройдены!")

test_edge_cases()

Рекомендации для интервью

Порядок решения:

1. Начните с наивного подхода (цикл)

   • Просто и понятно
   • Показывает понимание задачи

2. Спросите о производительности

   • "Можем ли мы это оптимизировать?"

3. Предложите формулу

   • Покажите, что это арифметическая прогрессия
   • Выведите формулу вместе с интервьюером

4. Объясните O(1)

   • Не зависит от размера входных данных
   • Только несколько операций

Резюме

Сумма чётных чисел от 1 до N:

Формула: S = k × (k + 1), где k = n ÷ 2