Завдання про зниклі числа: як програмісти мислять логічно

У світі програмування логічні задачі займають особливе місце. Вони тренують мислення, розвивають уміння аналізувати дані та шукати приховані залежності. Однією з таких класичних задач є задача про зниклі числа. Вона зустрічається на співбесідах, в олімпіадах і навіть у реальних проєктах, коли доводиться шукати відсутні елементи серед великих масивів даних.

Її формулювання таке. Нехай у нас є масив чисел від 1 до N, але одне або кілька чисел відсутні. Завдання полягає в тому, щоб знайти зниклі числа. Незважаючи на просте формулювання, існує безліч рішень, і кожне з них демонструє різні способи мислення програміста.

Класична постановка

Уявіть масив чисел: [1, 2, 3, 5, 6]. Очевидно, що відсутнє число 4. Але що, якщо масив містить мільйон елементів? Що, якщо відсутнє не одне число, а три? І що, якщо значення йдуть не підряд, а з випадковими пропусками?

Наша мета — побудувати алгоритм, який зможе визначити всі зниклі значення і зробити це максимально ефективно.

Підхід 1. Арифметична логіка

Найпростіший логічний підхід — використання суми чисел. Якщо відома формула суми натуральних чисел від 1 до N, можна обчислити очікувану суму і відняти фактичну.

def missing_number(nums):
	N = len(nums) + 1
	expected_sum = N * (N + 1) // 2
	actual_sum = sum(nums)
	return expected_sum - actual_sum

print(missing_number([1, 2, 3, 5, 6])) # Вивід: 4

Цей спосіб чудово працює для пошуку одного зниклого числа. Він логічний, простий і має високу продуктивність. Але в нього є обмеження — він не підходить для пошуку кількох зниклих значень.

Підхід 2. Булевий масив

Коли потрібно знайти кілька відсутніх чисел, логічним рішенням стає використання булевого масиву або словника, щоб позначити знайдені елементи.

function missingNumbers(arr, n) {
	const seen = Array(n + 1).fill(false);
	arr.forEach(num => seen[num] = true);

	const result = [];
	for (let i = 1; i <= n; i++) {
		if (!seen[i]) result.push(i);
	}
	return result;
}

console.log(missingNumbers([1, 2, 4, 6], 6)); // [3, 5]

Такий алгоритм використовує додаткову пам’ять, але зате він універсальний і працює незалежно від кількості зниклих значень. Це класичний приклад логічного підходу: раз числа трапляються від 1 до N, отже кожне можна позначити як «зустрілося» або «ні».

Підхід 3. Логіка XOR

Ще один цікавий і часом недооцінений підхід — використання операції XOR. Вона дозволяє ефективно знайти одне зникле значення без використання додаткової пам’яті.

Основна логіка проста: якщо «виключити» через XOR усі числа від 1 до N, а потім виключити всі числа з масиву, то залишиться лише зникле число.

def missing_number_xor(nums):
	xor_full = 0
	xor_arr = 0

	N = len(nums) + 1

	for i in range(1, N + 1):
		xor_full ^= i

	for num in nums:
		xor_arr ^= num

	return xor_full ^ xor_arr

print(missing_number_xor([1, 2, 3, 5, 6])) # 4

Цей варіант не лише логічний, а й математично елегантний. Він показує приклади того, як програмісти використовують властивості операцій для оптимізації рішень.

Практичний зв’язок із реальними проєктами

У реальних продуктах задачі пошуку пропусків трапляються набагато частіше, ніж здається. Наприклад, коли потрібно знайти зниклі ID користувачів, події, часові інтервали, пропуски в даних логування чи транзакціях. Такі проблеми виникають в аналітиці, обробці потоків даних і системах моніторингу.

Програміст може використовувати перелічені підходи для аналізу великих масивів, оптимізації збору даних і виявлення помилок у потоках інформації. Задача про зниклі числа — це не просто абстракція, а один із базових інструментів логічного мислення розробника.

Чому така логіка важлива

Логічні задачі тренують мислення. Вони допомагають розвивати уважність, уміння працювати з патернами, аналізувати дані та обирати правильний алгоритм для конкретної ситуації. Усе це — ключові якості програміста.

Розв’язуючи подібні задачі, розробник вчиться дивитися на дані як на послідовні структури, де кожне значення має своє місце. Це розвиває вміння швидко знаходити проблеми або невідповідності в коді та даних.