🛠 Алгоритм Действий
Весь секрет в сложении!
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))!
Расскажите в комментариях, что получилось у вас!
👉 | #задача
