Как найти пропущенное число в массиве

Учитывая массив n-1 различные целые числа в диапазоне от 1 до n, найти в нем пропущенное число за линейное время.

Например, рассмотрим массив {1, 2, 3, 4, 5, 7, 8, 9, 10} элементы которого различны и находятся в диапазоне от 1 до 10. Недостающее число — 6.

Потренируйтесь в этой проблеме

1. Использование формулы для суммы первых n Натуральные числа

Мы знаем, что сумма первых n натуральные числа можно вычислить по формуле 1 + 2 + … + n = n×(n+1)/2. Мы можем использовать эту формулу, чтобы найти пропущенное число.

Идея состоит в том, чтобы найти сумму целых чисел от 1 до n+1 используя приведенную выше формулу, где n размер массива. Также вычислите фактическую сумму целых чисел в массиве. Теперь недостающее число будет разницей между ними.

Этот подход демонстрируется ниже на C, Java и Python:

2. Использование оператора XOR

Мы знаем, что XOR двух одинаковых чисел отменяет друг друга. Мы можем воспользоваться этим фактом, чтобы найти недостающее число в массиве с ограниченным диапазоном.

Идея состоит в том, чтобы вычислить XOR всех элементов массива и вычислить XOR всех элементов от 1 до n+1, куда n размер массива. Теперь недостающее число будет XOR между ними.

Этот подход демонстрируется ниже на C, Java и Python:

Временная сложность обоих рассмотренных выше методов составляет O(n) и не требует дополнительного места, где n это размер ввода.

Let the given array be A with length N. Lets assume in the given array, the single empty slot is filled with 0.

We can find the solution for this problem using many methods including algorithm used in Counting sort. But, in terms of efficient time and space usage, we have two algorithms. One uses mainly summation, subtraction and multiplication. Another uses XOR. Mathematically both methods work fine. But programatically, we need to assess all the algorithms with main measures like

• Limitations(like input values are large(A[1...N]) and/or number of
  input values is large(N))
• Number of condition checks involved
• Number and type of mathematical operations involved

etc. This is because of the limitations in time and/or hardware(Hardware resource limitation) and/or software(Operating System limitation, Programming language limitation, etc), etc. Lets list and assess the pros and cons of each one of them.

Algorithm 1 :

In algorithm 1, we have 3 implementations.

1. Calculate the total sum of all the numbers(this includes the unknown missing number) by using the mathematical formula(1+2+3+...+N=(N(N+1))/2). Here, N=100. Calculate the total sum of all the given numbers. Subtract the second result from the first result will give the missing number.

   Missing Number = (N(N+1))/2) - (A[1]+A[2]+...+A[100])

2. Calculate the total sum of all the numbers(this includes the unknown missing number) by using the mathematical formula(1+2+3+...+N=(N(N+1))/2). Here, N=100. From that result, subtract each given number gives the missing number.

   Missing Number = (N(N+1))/2)-A[1]-A[2]-...-A[100]

   (Note:Even though the second implementation’s formula is derived from first, from the mathematical point of view both are same. But from programming point of view both are different because the first formula is more prone to bit overflow than the second one(if the given numbers are large enough). Even though addition is faster than subtraction, the second implementation reduces the chance of bit overflow caused by addition of large values(Its not completely eliminated, because there is still very small chance since (N+1) is there in the formula). But both are equally prone to bit overflow by multiplication. The limitation is both implementations give correct result only if N(N+1)<=MAXIMUM_NUMBER_VALUE. For the first implementation, the additional limitation is it give correct result only if Sum of all given numbers<=MAXIMUM_NUMBER_VALUE.)

3. Calculate the total sum of all the numbers(this includes the unknown missing number) and subtract each given number in the same loop in parallel. This eliminates the risk of bit overflow by multiplication but prone to bit overflow by addition and subtraction.

   //ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)
{
missingNumber = missingNumber + index;
//Since, the empty slot is filled with 0,
//this extra condition which is executed for N times is not required.
//But for the sake of understanding of algorithm purpose lets put it.
if (inputArray[index] != 0)
missingNumber = missingNumber - inputArray[index];
}

In a programming language(like C, C++, Java, etc), if the number of bits representing a integer data type is limited, then all the above implementations are prone to bit overflow because of summation, subtraction and multiplication, resulting in wrong result in case of large input values(A[1...N]) and/or large number of input values(N).

Algorithm 2 :

We can use the property of XOR to get solution for this problem without worrying about the problem of bit overflow. And also XOR is both safer and faster than summation. We know the property of XOR that XOR of two same numbers is equal to 0(A XOR A = 0). If we calculate the XOR of all the numbers from 1 to N(this includes the unknown missing number) and then with that result, XOR all the given numbers, the common numbers get canceled out(since A XOR A=0) and in the end we get the missing number. If we don’t have bit overflow problem, we can use both summation and XOR based algorithms to get the solution. But, the algorithm which uses XOR is both safer and faster than the algorithm which uses summation, subtraction and multiplication. And we can avoid the additional worries caused by summation, subtraction and multiplication.

In all the implementations of algorithm 1, we can use XOR instead of addition and subtraction.

Lets assume, XOR(1...N) = XOR of all numbers from 1 to N

Implementation 1 => Missing Number = XOR(1...N) XOR (A[1] XOR A[2] XOR...XOR A[100])

Implementation 2 => Missing Number = XOR(1...N) XOR A[1] XOR A[2] XOR...XOR A[100]

Implementation 3 =>

//ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)
{
    missingNumber = missingNumber XOR index;
    //Since, the empty slot is filled with 0,
    //this extra condition which is executed for N times is not required.
    //But for the sake of understanding of algorithm purpose lets put it.
    if (inputArray[index] != 0)
        missingNumber = missingNumber XOR inputArray[index];
}

All three implementations of algorithm 2 will work fine(from programatical point of view also). One optimization is, similar to

1+2+....+N = (N(N+1))/2

We have,

1 XOR 2 XOR .... XOR N = {N if REMAINDER(N/4)=0, 1 if REMAINDER(N/4)=1, N+1 if REMAINDER(N/4)=2, 0 if REMAINDER(N/4)=3}

We can prove this by mathematical induction. So, instead of calculating the value of XOR(1…N) by XOR all the numbers from 1 to N, we can use this formula to reduce the number of XOR operations.

Also, calculating XOR(1…N) using above formula has two implementations. Implementation wise, calculating

// Thanks to https://a3nm.net/blog/xor.html for this implementation
xor = (n>>1)&1 ^ (((n&1)>0)?1:n)

is faster than calculating

xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;

So, the optimized Java code is,

long n = 100;
long a[] = new long[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);
long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

for (long i = 0; i < n; i++)
{
    xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);

Ввод: nums = [3,0,1]
Вывод: 2
Пояснение: n = 3, так как всего элементов в массиве три, поэтому все элементы 
находятся в диапазоне [0,3]. 2 — недостающий элемент.

Ввод: nums = [0,1]
Вывод: 2
Пояснение: n = 2, так как всего элементов в массиве два, поэтому все элементы 
находятся в диапазоне [0,2]. 2 — недостающий элемент.

Ввод: nums = [9,6,4,2,3,5,7,0,1]
Вывод: 8
Пояснение: n = 9, так как всего элементов в массиве девять, поэтому все элементы 
находятся в диапазоне [0,9]. 8 — недостающий элемент.

public int missingNumber(int[] nums) {
    int realSum = 0;
    int sum = 0;

    for (int num : nums) {
        sum += num;
    }

    for (int i = 0; i <= nums.length; i++) {
        realSum += i;
    }
    return realSum - sum;
}

public int missingNumber(int[] nums) {
    int rez = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += (i + 1);
        rez += nums[i];
    }
    return sum - rez;
}

Научитесь: Профессия Java-разработчик
Узнать больше

Один из наиболее часто задаваемых вопросов на собеседованиях — найти пропущенное число в массиве на Java, C # или любом другом языке. Такого рода вопросы задаются не только в небольших стартапах, но и в некоторых крупнейших технических компаниях, таких как Google, Amazon, Facebook, Microsoft.

В простейшей версии этого вопроса надо найти недостающий элемент в массиве целых чисел, содержащем числа от 1 до 100. Это можно легко решить, вычислив предполагаемую сумму с помощью n (n + 1) /2 и отняв от нее сумму всех существующих элементов массива. Это также один из самых быстрых и эффективных способов, но его нельзя использовать, если массив содержит более одного пропущенного числа или если массив содержит дубликаты.

Это дает интервьюеру несколько хороших намеков, чтобы проверить, может ли кандидат применить свои знания в несколько иных состояниях или нет. Поэтому, если вы справитесь с первым подходом, вас попросят найти пропущенное число в массиве с дубликатами или с несколькими пропущенными числами. Это может быть более сложно, но вы скоро обнаружите, что другой способ найти пропущенное и повторяющееся число в массиве — это отсортировать его.

В отсортированном массиве вы можете сравнить, равно ли число ожидаемому следующему числу или нет.

Кроме того, вы также можете использовать BitSet в Java для решения этой проблемы — надо перебрать все записи и использовать набор битов, чтобы запомнить, какие числа установлены, а затем проверить на 0 бит. Запись с битом 0 является отсутствующим номером.

Найти пропущенное число в массиве: решение на Java

import java.util.Arrays;
import java.util.BitSet;
 
public class MissingNumberInArray {
 
    public static void main(String args[]) {

        // one missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6}, 6);
 
        // two missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
 
        // three missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
 
        // four missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 9, 8}, 10);
 
        // Only one missing number in array
        int[] iArray = new int[]{1, 2, 3, 5};
        int missing = getMissingNumber(iArray, 5);
        System.out.printf("Missing number in array %s is %d %n",

                           Arrays.toString(iArray), missing);
    }

   /**
    * A general method to find missing values from an integer array in Java.
    * This method will work even if array has more than one missing element.
    */
    private static void printMissingNumber(int[] numbers, int count) {
        int missingCount = count - numbers.length;
        BitSet bitSet = new BitSet(count);
 
        for (int number : numbers) {
            bitSet.set(number - 1);
        }
 
        System.out.printf("Missing numbers in integer array %s, with total number %d is %n",
        Arrays.toString(numbers), count);
        int lastMissingIndex = 0;

        for (int i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
 
    }

   /**
    * Java method to find missing number in array of size n containing

    * numbers from 1 to n only.
    * can be used to find missing elements on integer array of

    * numbers from 1 to 100 or 1 - 1000
    */
    private static int getMissingNumber(int[] numbers, int totalCount) {
        int expectedSum = totalCount * ((totalCount + 1) / 2);
        int actualSum = 0;
        for (int i : numbers) {
            actualSum += i;
        }
 
        return expectedSum - actualSum;
    }
 
}

Алгоритм с XOR

Мы можем использовать свойство XOR, чтобы получить решение этой проблемы, не беспокоясь о проблеме переполнения битов. Кроме того, XOR безопаснее и быстрее суммирования. Мы знаем свойство XOR, что XOR двух одинаковых чисел равен 0 ( A XOR A = 0). Если мы вычислим XOR всех чисел от 1 до N (это включает в себя неизвестное пропущенное число), а затем с этим результатом, XOR всех заданных чисел, общие числа будут отменены (так как A XOR A=0), и в конце мы получим пропущенное число. Если у нас нет проблемы переполнения битов, мы можем использовать как суммирование, так и алгоритмы на основе XOR, чтобы получить решение. Но алгоритм, использующий XOR, безопаснее и быстрее, чем алгоритм, который использует суммирование, вычитание и умножение. И мы можем избежать дополнительных забот, вызванных суммированием, вычитанием и умножением.

long n = 100;
long a[] = new long[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

for (long i = 0; i < n; i++)
{
   xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);

Если вы нашли опечатку — выделите ее и нажмите Ctrl + Enter! Для связи с нами вы можете использовать info@apptractor.ru.

Если размер массива достаточно большой, а предполагаемое число пропущенных элементов не велико, можно еще и такой вариант.

$data = [1,2,5,6,9,11];

$prev = current($data);
$result = array_reduce($data, function($c, $item) use (&$prev){
                    if($item - $prev > 1){
                        $c = array_merge($c, range($prev + 1, $item - 1));
                    }
                    $prev = $item;
                    return $c;
                }, []);

А если специфика задачи такова, что у нас очень большой массив и получается очень много пропущенных значений (и не очень большом числе самих пропущенных интервалов), что использование функции range тратит не оправдано много памяти, то как по классическому примеру из справки по использованию генераторов можем сделать следующее:

$result =  function($data){
                $prev = current($data);
                $ranges = array_reduce($data, function($c, $item) use (&$prev){
                            if($item - $prev > 1)   $c[] = [$prev+1, $item -1];
                            $prev = $item;
                            return $c;
                          }, []);
                foreach($ranges as list($l, $h)){
                     while($l <= $h) yield $l++;
                }
            };

foreach($result($data) as $x) echo $x, "n";

в этом случае память будет тратится только на хранение пар значений, обозначающих края пропущенных отрезков.