Часто задаваемая головоломка на собеседованиях по Java – поиск недостающего числа из ряда или массива чисел. Эта головоломка была задана в интервью, проведенном на Amazon.com.
1. Проблема
В этой головоломке Java у нас есть ряд чисел, начинающихся(например, 1….N), и ровно одно число в этом ряду отсутствует. Нам нужно написать программу Java, чтобы найти недостающее число в ряду.
Например, в следующей серии отсутствует число 10.
Series: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12Missing Number: 10
2. Решение
Удивительно, но решение этой головоломки очень простое, только если мы его уже знаем.
- Вычислите A = n(n+1)/2, где n — наибольшее число в ряду 1…N.
- Вычислите B = сумму всех чисел в данной серии
- Пропущенное число = A – B
Давайте запишем решение в коде.
import java.util.Arrays;public class FindMissingNumberFromSeries {public static void main(String[] args) {int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12};int N = numbers[numbers.length-1]; //The last element in the arrayint expectedSum =(N *(N + 1)) / 2;int actualSum = Arrays.stream(numbers).sum();int missingNumber = expectedSum - actualSum;System.out.println(missingNumber);}}Такие головоломки легко решать, но всегда полезно знать решение до того, как его спросят на собеседовании. Так что будьте готовы найти недостающие числа в массиве на следующем собеседовании.