🛠 Алгоритм Действий

Весь секрет в сложении!

1. Считаем, сколько должно быть:
Используем формулу для суммы чисел от 1 до N. Это наша Полная Сумма.

Полная Сумма = N*(N + 1)/2

2. Считаем, сколько есть:
Проходим по нашему массиву один раз и складываем все числа. Это наша Фактическая Сумма.

3. Находим разницу:
Вычитаем то, что есть, из того, что должно быть.

Пропущенное число = Полная Сумма - Фактическая Сумма

💻 Реализация на Java

public class Main {
    public static void main(String[] args) {
        // Задаем N - максимальное число, которое должно быть в последовательности.
        int n = 10; 

        // Массив, в котором отсутствует одно число (например, 3)
        // int[] array = new int[] {1, 2, 4, 5, 6, 7, 8, 9, 10}; // Если 3 пропущено
        int[] array = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Тестовый массив без пропусков

        // 1. Вычисляем Полную Сумму (Full Sum)
        // Используем формулу суммы арифметической прогрессии: N * (N + 1) / 2
        // Это эталонная сумма всех чисел от 1 до N.
        int sumAll = (n * (n + 1)) / 2;

        // 2. Вычисляем Фактическую Сумму (Actual Sum) за один проход
        int sum = 0;
        // Это единственный проход по массиву, соответствующий ограничению O(N)
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }

        // 3. Сравниваем суммы и выводим результат
        if (sumAll == sum) {
            System.out.println("Число не пропущено");
        } else {
            // Разница между полной и фактической суммой - это и есть пропущенное число.
            System.out.println("Пропущено число: " + (sumAll - sum));
        }
    }
}

Это решение — идеальный ответ на собеседовании. 😉

Оно демонстрирует не только умение писать код, но и знание базовой математики, позволяющее создать алгоритм с оптимальной временной сложностью (O(N)) и пространственной сложностью (O(1))!

Расскажите в комментариях, что получилось у вас!

👉 Java Rocks | #задача