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

Given an array of n unique integers where each element in the array is in the range [1, n]. The array has all distinct elements and the size of the array is (n-2). Hence Two numbers from the range are missing from this array. Find the two missing numbers.

Examples : 

Input  : arr[] = {1, 3, 5, 6}
Output : 2 4

Input : arr[] = {1, 2, 4}
Output : 3 5

Input : arr[] = {1, 2}
Output : 3 4

Method 1 – O(n) time complexity and O(n) Extra Space

Step 1: Take a boolean array mark that keeps track of all the elements present in the array. 
Step 2: Iterate from 1 to n, check for every element if it is marked as true in the boolean array, if not then simply display that element.

Two Missing Numbers are
2 4 

Method 2 – O(n) time complexity and O(1) Extra Space

The idea is based on this popular solution for finding one missing number. We extend the solution so that two missing elements are printed. 
Let’s find out the sum of 2 missing numbers:

arrSum => Sum of all elements in the array

sum (Sum of 2 missing numbers) = (Sum of integers from 1 to n) - arrSum
                               = ((n)*(n+1))/2 – arrSum 

avg (Average of 2 missing numbers) = sum / 2;

• One of the numbers will be less than or equal to avg while the other one will be strictly greater than avg. Two numbers can never be equal since all the given numbers are distinct.
• We can find the first missing number as a sum of natural numbers from 1 to avg, i.e., avg*(avg+1)/2 minus the sum of array elements smaller than avg
• We can find the second missing number by subtracting the first missing number from the sum of missing numbers

Consider an example for better clarification 

Input : 1 3 5 6, n = 6
Sum of missing integers = n*(n+1)/2 - (1+3+5+6) = 6.
Average of missing integers = 6/2 = 3.
Sum of array elements less than or equal to average = 1 + 3 = 4
Sum of natural numbers from 1 to avg = avg*(avg + 1)/2
                                     = 3*4/2 = 6
First missing number = 6 - 4 = 2
Second missing number = Sum of missing integers-First missing number
Second missing number = 6-2= 4

Below is the implementation of the above idea.

Two Missing Numbers are
2 4

Note: There can be overflow issues in the above solution. 

In below set 2, another solution that is O(n) time, O(1) space, and doesn’t cause overflow issues is discussed.
Find Two Missing Numbers | Set 2 (XOR based solution)

This article is contributed by Chirag Agarwal. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. 

Last Updated :
05 Jul, 2022

Like Article

Save Article

Есть интересная задача: есть массив целых чисел. Числа идут подряд от 1 до k. Но в
массиве пропущены два числа. Как найти эти числа?

Решил поделиться своим решением и реализацией (на Ruby) самого простого из них (еще два приведу в виде алгоритмов).

Способ 1.

Первое что приходит в голову — использовать индексы у массива.

Допустим у нас есть такой массив

enter_arr = [1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19]

Тогда индексы будут следовать от 0 до 16 включительно.
Очевидно воспользоваться разницей между значением массива и индексом.

1) Если число на своем месте, то разница будет 1
2) Если пропущено одно число, то значение в массиве сдвинется влево и разница будет 2
3) Если пропущены оба, то разница больше 2

Итак, идея проста, реализуем ее

# Способ 1. Воспользуемся индексом. Ищем разницу между индексом и значением.
class ArrFinder1
  def initialize(array_arg)
    @array_arg = array_arg
  end
  def array_each_helper arr, diff
    array_cut = []
    stopindex = -1
    stopnumber = -1
    arr.each_with_index do |elem,index|
        var = elem-index
          if var > diff
            stopindex = index; stopnumber = elem; break
          end
        array_cut << elem # обрезаем массив если надйено значение и пишем в него то что осталось
      end
    [stopindex, stopnumber, array_cut]
  end 
  def find_empty
    p "Input array:"
    p @array_arg

    stopindex1, stopnumber1, array_arg_cut =  array_each_helper(@array_arg, 2)
        
    # Смотрим, может пропущены 2 числа подряд
    if stopnumber1 - array_arg_cut[-1] == 3
      number1 = stopnumber1-1
      number2 = stopnumber1-2
    else
      number1 = @array_arg[stopindex1]-1
      stopindex2, stopnumber2 =  array_each_helper(array_arg_cut, 1)
      number2 = stopnumber2-1   
    end
        
    p "missing numbers:"
    p number1
    p number2   
  end   
end

Вызываем

obj = ArrFinder1.new enter_arr
obj.find_empty

Результат:

"Input array:"
[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19]
"missing numbers:"
12
3

Способ 2.

Однако решил усовершенствовать способ, обрезая массив пополам.

Алгоритм.
1) Выбираем середину массива и смотрим разницу в контрольной точке.
1.1) Если разница больше 2, значит пропущенные числа в первой половине.
1.2) Если равно 2, то пропущенное число 1 перед, другое после.
1.3) Если разница больше 1, то оба числа находятся дальше.
2) Если случай п.1.1, то берем первую половину массива и выбираем точку посередине и также смотрим значение разницы в ней. Далее смотрим как в п.1.1, 1.2, 1.3. Аналогично, если п.1.3, только берем вторую половину.
3) Если случай п.1.2 Выбираем середину массива первой половины и смотрим разницу в контрольной точке. Теперь уже смотрим разница больше ли 1. Если да, то повторяем п.3. Если нет то снова делим вторую часть и повторяем рекурсвивно действия как в начале пункта. До тех пор пока не найдем точку

Из преимуществ — нет необходимости пробегать весь массив, а сразу выбирать репперные точки. Что должно ускорить процесс. Также в данном подходе будет рекурсия, что упростит код.

Способ 3.

В принципе можно разложить каждое число побитово, получится примерно такое:

#0000 — ноля в задаче нет, но для наглядности напишу его тоже
0001
0010
0011

0100
0101
0110
0111

1000
1001
1010
1011
и т.д.

Как видим нам нужны первые два разряда числа.
Первый разряд идет последовательно 0-1-0-1, второй 0-0-1-1
Итак, если число пропущено, то будет смещение. Например, пропущено 2, тогда последовательность первого разряда (ноль тоже включу) 0-1-1-0, второго 0-0-1-0.
Таким образом несложно определить какое число пропущено.
Если пропущены 2 подряд, то смещение первого разряда не произойдет, но мы по смещению второго определим сдвиг: 0-0-0-0

Какие еще есть рациональные способы на Ваш взгляд?

Автор: Jeket

Этот метод не рекомендуется, так как он страдает от проблем с переполнением integer. Поэтому используйте метод XOR, чтобы найти два числа, которые очень эффективны. Если вам интересно, я могу объяснить.

В соответствии с запросом @ordinary ниже я объясняю алгоритм:

ИЗМЕНИТЬ

Предположим, что максимальный элемент массива a[] равен B i.e предположим a[]={1,2,4}, и здесь 3 и 5 не присутствуют в [], поэтому максимальный элемент B=5.

• XOR все элементы массива a — X
• XOR все элементы от 1 до B до X
• найдите самый старший бит из X на x = x &(~(x-1));
• Теперь, если a[i] ^ x == x чем XOR a[i] до p else XOR с q
• Теперь для всех k от 1 до B, если k ^ x == x чем XOR с p else XOR с q
• Теперь напечатайте p и q

доказательство:

Пусть a = {1,2,4} и B равно 5, то есть от 1 до 5 недостающих чисел 3 и 5

Как только мы XOR элементы a и числа от 1 до 5, мы оставили с XOR 3 и 5, т.е. X.

Теперь, когда мы находим самый левый бит-набор из X, это не что иное, как самый левый бит между 3 и 5. (3--> 011, 5 --> 101 и x = 010 где x = 3 ^ 5)

После этого мы пытаемся разделить на две группы в соответствии с набором бит X, поэтому две группы будут:

p = 2 , 2 , 3 (all has the 2nd last bit set)

q = 1, 1, 4, 4, 5 (all has the 2nd last bit unset)

если мы XOR элементы p между собой, найдем 3 и аналогично, если мы XOR все элементы q между собой, чем получим 5.
Отсюда и ответ.

код в java

public void findNumbers(int[] a, int B){
    int x=0;
    for(int i=0; i<a.length;i++){
        x=x^a[i];
    }
    for(int i=1;i<=B;i++){
        x=x^i;
    }
    x = x &(~(x-1));
    int p=0, q=0;
    for(int i=0;i<a.length;i++){
        if((a[i] & x) == x){
            p=p^a[i];
        }
        else{
            q=q^a[i];
        }   
    }
    for(int i=1;i<=B;i++){
        if((i & x) == x){
            p=p^i;
        }
        else{
            q=q^i;
        }
    }

    System.out.println("p: "+p+" : "+q);
}

Далее представлен калькулятор, при помощи которого можно искать пропущенные номера в последовательности целых чисел. Пример такой последовательности (каждое число на новой строке):

1
2
3
4
6
7
12
13
18
Как видно в последовательности есть пропуски и единичных номеров и нескольких подряд следующих номеров. Например, номер 5 пропущен, а также пропущено два куска: между 8 и 11 и между 14 и 17.

В таком простом примере Вы и сами можете найти пропуски, но если речь идет о тысячах номеров, то калькулятор вам сильно пригодится. Просто скопируйте вашу последовательность в текстовое поле и калькулятор найдет все пропуски между числом в первой и последней строках.

Настройки калькулятора пропусков

Для более сложных случаев имеется несколько настроек:

• Установите флажек «В сжатом виде» чтобы калькулятор выдавал диапазоны последовательных пропусков номеров, например 8 — 11, где 8 начало, а 11 конец последовательного пропуска. В противном случае будет выдана вся последовательность пропущенных номеров, например 8, 9, 10, 11.
• Можно установить галочку «Использовать регулярные выражения для выделения номеров», для выделения чисел из строки при помощи регулярного выражения.

Последняя опция становится актуальной, если в вашем перечне номеров содержатся не только числа, например вот такая последовательность:
1 Бумага побеждает камень
2 Ножницы режут бумагу
3 Камень разрушает ножницы

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

Алгоритм
нахождения пропущенного числа в начальной школе.

Мой педагогический
стаж 35 лет. Из них 34 года я проработала учителем начальных классов.
Педагогический опыт достаточно большой.  За время работы мною найдены такие
приёмы организации учебной деятельности, благодаря которым  основные понятия
программного материала как по русскому языку, так и по математике легко
воспринимаются и усваиваются учащимися с различным уровнем обученности.

    Совсем недавно
я стала работать  методистом по практике в Костанайском педагогическом
колледже.  Достаточно часто во время подготовки и  проведении зачётных уроков,
я сталкиваюсь с тем, что студенты нацеливают свою работу только на то, чтобы
выполнить задание — решить задачу, уравнение, найти значение выражения;
просклонять имя существительное, разобрать слово по составу и т. д. Но не
понимают, что очень важно научить детей анализировать задание и найти способ
его выполнения. А как это важно!

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

     Итак,
достаточно часто в учебники по математике включают задания со звёздочкой вида:

… — 5 = 4,
 … + 4 = 9,   9 — … = 6.

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

ð  От какого числа
нужно отнять 5, чтобы получилось 4?

ð  Ребята вспоминают
состав числа 9. 9 — это 5 и 4. 

ð  От 9  отнимаем 5,
остаётся 4.

ð  Значит пропущенное
число — 4.

ð  И так далее. 

    Но вот задания
усложняются и появляются задания вида:

10 —  … +
3= 4 

или

10 —  …
+ 3 + 4 = 8

и ещё сложнее

10 —  …
+ 3 + 4 — 6 +5 = 7

Как быть ученику? 
Подбирать до бесконечности, пока не подойдёт одно из чисел?

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

    Я предлагаю
вникнуть в процесс анализа следующего выражения: 10 —  … + 3= 4.
Начнем с последнего действия.

       1

10 — … + 3 = 4

То, что закрашено
красным цветом, закрываем и представляем как один компонент — неизвестное число
(неизвестный компонент -слагаемое).  Задаём детям вопрос: к какому числу
(слагаемому) нужно +3, чтобы стало 4? Конечно же к 1 (выделим жёлтым цветом).
Значит в той части, которая закрашена красным цветом  (10-…) должно в результате
получится 1.

10-…=1 Нужно от
10  отнять 9, чтобы получилось  число 1. Вот и пришли к искомому числу.

Проверим — 10
—  9 + 3= 4. Всё верно.

      Рассмотрим
более сложное выражение: 10 —  … + 3 + 4 — 6 +5 = 7

Анализ и
рассуждение начнём снова с конца.

10 — … + 3 + 4 – 6 + 5 = 7

Снова закрываем
всю запись до последнего действия. Рассуждаем так: к какому числу нужно
прибавить 5, чтобы получилось 7? Отвечаем: к 2.

Надписываем над
предпоследним действием  число 2.

                       
2

10 — … + 3 + 4 – 6 + 5 = 7

Продвигаемся в
своём рассуждении дальше.

                       
2

10 — … + 3 + 4 – 6 + 5 = 7

Что закрашено
красным цветом- неизвестное число (или неизвестное уменьшаемое). От какого
числа нужно отнять 6, чтобы получилось 2? От 8. Надписываем над предпоследним действием.

                  
8    2

10 — … + 3 + 4 – 6 + 5 = 7

Рассуждаем дальше.

К какому числу
(слагаемому) нужно прибавить 4, чтобы получилось 8?  К 4.

Надписываем над
предпоследним действием 4. (выделено жёлтым цветом)

            
4    8   

10 — … + 3 + 4

Идём дальше.  К
какому числу нужно прибавить 3, чтобы в ответе получилось 4? К 1. Значит над
первым действием надписываем число 1 (выделено жёлтым цветом).

        1  4       

10 — … + 3  

Вот и завершающий
этап. Сколько нужно отнять от 10, чтобы получить 1? Конечно же 9. Вставляем в
пустую клетку число 9.

     1        

10 — 9

И проверяем всё
выражение.

     1   
4    8    2    7

10 – 9 + 3
+ 4 – 6 + 5 = 7

Пропущенное число найдено. Так можно вести
рассуждение с любыми числами — от однозначного до многозначных. Попробуйте.
Действует.

1123095 — … + 347820 — 56208 + 3456=
935501

У меня получился ответ: 182662

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