Рубрики

Найти два недостающих номера | Набор 1 (Интересное решение с линейным временем)

Дан массив из n уникальных целых чисел, где каждый элемент в массиве находится в диапазоне [1, n]. Массив имеет все отдельные элементы, а размер массива равен (n-2). Следовательно, два числа из диапазона отсутствуют в этом массиве. Найдите два пропущенных числа.

Примеры :

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

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

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

Метод 1 — O (n) сложность времени и O (n) дополнительное пространство

Шаг 1: Возьмите метку логического массива, которая отслеживает все элементы, присутствующие в массиве.
Шаг 2. Итерируйте от 1 до n, проверьте для каждого элемента, отмечен ли он как истинный в логическом массиве, если нет, просто отобразите этот элемент.

C ++

// Программа на C ++ для поиска двух пропущенных чисел с помощью O (n)
// дополнительное пространство
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска двух пропущенных чисел в диапазоне
// [1, n]. Эта функция предполагает, что размер массива
// это n-2 и все элементы массива различны

void findTwoMissingNumbers(int arr[], int n)

{

    // Создаем логический вектор размером n + 1 и

    // отметить все присутствующие элементы arr [] в нем.

    vector<bool> mark(n+1, false);

    for (int i = 0; i < n-2; i++)

        mark[arr[i]] = true;

  

    // Распечатать два неотмеченных элемента

    cout << "Two Missing Numbers are\n";

    for (int i = 1; i <= n; i++)

       if (! mark[i])

           cout << i << " ";

  

    cout << endl;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {1, 3, 5, 6};

  

    // Диапазон чисел 2 плюс размер массива

    int n = 2 + sizeof(arr)/sizeof(arr[0]);

  

    findTwoMissingNumbers(arr, n);

  

    return 0;

}

Джава

// Java-программа для поиска двух пропущенных чисел, используя O (n)
// дополнительное пространство

import java.util.*;

  

class GFG

{

  
// Функция для поиска двух пропущенных чисел в диапазоне
// [1, n]. Эта функция предполагает, что размер массива
// это n-2 и все элементы массива различны

static void findTwoMissingNumbers(int arr[], int n) 

    // Создаем логический вектор размером n + 1 и

    // отметить все присутствующие элементы arr [] в нем.

    boolean []mark = new boolean[n+1]; 

    for (int i = 0; i < n-2; i++) 

        mark[arr[i]] = true

  

    // Распечатать два неотмеченных элемента

    System.out.println("Two Missing Numbers are"); 

    for (int i = 1; i <= n; i++) 

    if (! mark[i]) 

        System.out.print(i + " "); 

  

    System.out.println();

  
// Код драйвера

public static void main(String[] args) 

{

    int arr[] = {1, 3, 5, 6}; 

  

    // Диапазон чисел 2 плюс размер массива

    int n = 2 + arr.length; 

  

    findTwoMissingNumbers(arr, n); 

}
}

  
// Этот код предоставлен 29AjayKumar

python3

# Программа Python3 для поиска двух пропущенных чисел с помощью O (n)
# дополнительное место

  
# Функция для поиска двух пропущенных чисел в диапазоне
# [1, n]. Эта функция предполагает, что размер массива
# равно n-2, и все элементы массива различны

def findTwoMissingNumbers(arr, n):

    # Создайте логический вектор размера n + 1 и

    # отметить все присутствующие элементы arr [] в нем.

    mark = [False for i in range(n+1)]

    for i in range(0,n-2,1):

        mark[arr[i]] = True

  

    # Распечатать два неотмеченных элемента

    print("Two Missing Numbers are")

    for i in range(1,n+1,1):

        if (mark[i] == False):

            print(i,end = " ")

  

    print("\n")

  
# Программа драйвера для проверки вышеуказанной функции

if __name__ == '__main__':

    arr = [1, 3, 5, 6]

  

    # Диапазон чисел 2 плюс размер массива

    n = 2 + len(arr)

  

      

    findTwoMissingNumbers(arr, n);

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # Программа для поиска двух пропущенных номеров
// используя O (n) лишний пробел

using System;

using System.Collections.Generic; 

      

class GFG

{

  
// Функция для поиска двух пропущенных чисел в диапазоне
// [1, n]. Эта функция предполагает, что размер массива
// это n-2 и все элементы массива различны

static void findTwoMissingNumbers(int []arr, int n) 

    // Создаем логический вектор размером n + 1 и

    // отметить все присутствующие элементы arr [] в нем.

    Boolean []mark = new Boolean[n + 1]; 

    for (int i = 0; i < n - 2; i++) 

        mark[arr[i]] = true

  

    // Распечатать два неотмеченных элемента

    Console.WriteLine("Two Missing Numbers are"); 

    for (int i = 1; i <= n; i++) 

    if (! mark[i]) 

        Console.Write(i + " "); 

  

    Console.WriteLine();

  
// Код драйвера

public static void Main(String[] args) 

{

    int []arr = {1, 3, 5, 6}; 

  

    // Диапазон чисел 2 плюс размер массива

    int n = 2 + arr.Length; 

  

    findTwoMissingNumbers(arr, n); 

}
}

  
// Этот код предоставлен Rajput-Ji


Выход :

Two Missing Numbers are
2 4

Способ 2 — O (n) сложность времени и O (1) дополнительное пространство

Идея основана на этом популярном решении для поиска одного пропущенного числа. Мы расширяем решение так, чтобы два отсутствующих элемента были напечатаны.
Давайте выясним сумму 2 пропущенных чисел:

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;
  • Одним из чисел будет меньше или равна средн в то время как другой будет строго больше , то ср. Два числа никогда не могут быть равны, поскольку все данные числа различны.
  • Мы можем найти первое пропущенное число в виде суммы натуральных чисел от 1 до avg , т.е. avg * (avg + 1) / 2 минус сумма элементов массива, меньшая, чем avg
  • Мы можем найти второе пропущенное число, вычитая первое пропущенное число из суммы пропущенных чисел.

Рассмотрим пример для лучшего разъяснения

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

Ниже приведена реализация вышеуказанной идеи.

C ++

// Программа на C ++ для поиска 2 пропущенных чисел с помощью O (1)
// дополнительное пространство
#include <iostream>

using namespace std;

  
// Возвращает сумму массива

int getSum(int arr[],int n)

{

    int sum = 0;

    for (int i = 0; i < n; i++)

        sum += arr[i];

    return sum;

}

  
// Функция для поиска двух пропущенных чисел в диапазоне
// [1, n]. Эта функция предполагает, что размер массива
// это n-2 и все элементы массива различны

void findTwoMissingNumbers(int arr[],int n)

{

    // сумма 2 пропущенных чисел

    int sum = (n*(n + 1)) /2 - getSum(arr, n-2);

  

    // Находим среднее из двух элементов

    int avg = (sum / 2);

  

    // Находим сумму элементов меньше среднего (в среднем)

    // и сумма элементов больше среднего (в среднем)

    int sumSmallerHalf = 0, sumGreaterHalf = 0;

    for (int i = 0; i < n-2; i++)

    {

        if (arr[i] <= avg)

            sumSmallerHalf += arr[i];

        else

            sumGreaterHalf += arr[i];

    }

  

    cout << "Two Missing Numbers are\n";

  

    // Первый (меньший) элемент = (сумма натуральных

    // числа до avg) - (сумма элементов массива

    // меньше или равно avg)

    int totalSmallerHalf = (avg*(avg + 1)) / 2;

    int smallerElement = totalSmallerHalf - sumSmallerHalf;

    cout << smallerElement << " ";

  

    // Второй (больший) элемент = (сумма обоих

    // элементы) - меньший элемент

    cout << sum - smallerElement;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {1, 3, 5, 6};

   

    // Диапазон чисел 2 плюс размер массива

    int n = 2 + sizeof(arr)/sizeof(arr[0]);

   

    findTwoMissingNumbers(arr, n);

   

    return 0;

}

Джава

// Java программа для поиска 2 пропавших без вести
// Числа, использующие O (1) лишний пробел

import java.io.*;

  

class GFG 

{

      
// Возвращает сумму массива

static int getSum(int arr[], int n)

{

    int sum = 0;

    for (int i = 0; i < n; i++)

        sum += arr[i];

    return sum;

}

  
// Функция для поиска двух пропавших без вести
// числа в диапазоне [1, n]. Эта
// функция предполагает, что размер
// массив n-2 и весь массив
// элементы различны

static void findTwoMissingNumbers(int arr[], 

                                  int n)

{

    // сумма 2 пропущенных чисел

    int sum = (n * (n + 1)) /

               2 - getSum(arr, n - 2);

  

    // Находим среднее из двух элементов

    int avg = (sum / 2);

  

    // Находим сумму элементов меньше

    // чем среднее значение (в среднем) и сумма

    // элементы больше среднего (в среднем)

    int sumSmallerHalf = 0

        sumGreaterHalf = 0;

    for (int i = 0; i < n - 2; i++)

    {

        if (arr[i] <= avg)

            sumSmallerHalf += arr[i];

        else

            sumGreaterHalf += arr[i];

    }

  

    System.out.println("Two Missing "

                       "Numbers are");

  

    // Первый (меньший) элемент =

    // (сумма натуральных чисел до

    // avg) - (сумма элементов массива

    // меньше или равно avg)

    int totalSmallerHalf = (avg * 

                           (avg + 1)) / 2;

    System.out.println(totalSmallerHalf - 

                         sumSmallerHalf);

  

    // Первый (меньший) элемент =

    // (сумма натуральных чисел из

    // avg + 1 до n) - (сумма массива

    // элементы больше чем avg)

    System.out.println(((n * (n + 1)) / 2

                        totalSmallerHalf) - 

                           sumGreaterHalf);

}

  
// Код драйвера

public static void main (String[] args) 

{

int arr[] = {1, 3, 5, 6};

      
// Диапазон чисел равен 2
// плюс размер массива

int n = 2 + arr.length;

      
findTwoMissingNumbers(arr, n);
}
}

  
// Этот код предоставлен aj_36

python3

# Программа Python, чтобы найти 2 пропавших без вести
# Числа, использующие O (1) дополнительное пространство

  
# Возвращает сумму массива

def getSum(arr,n):

  

    sum = 0

    for i in range(0, n): 

        sum += arr[i] 

    return sum

  
# Функция поиска двух пропавших без вести
# числа в диапазоне [1, n]. Эта
# функция предполагает, что размер
# массив n-2 и весь массив
# элементы различны

def findTwoMissingNumbers(arr, n): 

  

    # Сумма 2 пропущенных чисел

    sum = ((n * (n + 1)) / 2 - 

           getSum(arr, n - 2)); 

  

    # Найти среднее из двух элементов

    avg = (sum / 2); 

  

    # Найти сумму элементов меньше

    # чем в среднем (в среднем) и сумма

    количество элементов больше чем

    # среднее (в среднем)

    sumSmallerHalf = 0

    sumGreaterHalf = 0

    for i in range(0, n - 2):

      

        if (arr[i] <= avg):

            sumSmallerHalf += arr[i]

        else:

            sumGreaterHalf += arr[i]

      

    print("Two Missing Numbers are"

  

    # Первый (меньший) элемент = (сумма

    # натуральных чисел до среднего) - (сумма

    Количество элементов массива меньше или

    # равно среднему)

    totalSmallerHalf = (avg * (avg + 1)) / 2

    print(str(totalSmallerHalf - 

              sumSmallerHalf) + " ")

  

    # Первый (меньший) элемент = (сумма

    # натуральных чисел от avg + 1 до n) -

    # (сумма элементов массива больше, чем avg)

    print(str(((n * (n + 1)) / 2 - 

               totalSmallerHalf) -

               sumGreaterHalf)) 

  
Код водителя

arr = [1, 3, 5, 6

      
# Диапазон номеров 2
# плюс размер массива

n = 2 + len(arr)

      
findTwoMissingNumbers(arr, n)

  
# Этот код добавлен
# Ятин Гупта

C #

// C # Программа для поиска 2 пропавших без вести
// Числа, использующие O (1) лишний пробел

using System;

  

class GFG

{

      
// Возвращает сумму массива

static int getSum(int []arr, int n)

{

    int sum = 0;

    for (int i = 0; i < n; i++)

        sum += arr[i];

    return sum;

}

  
// Функция для поиска двух пропавших без вести
// числа в диапазоне [1, n]. Эта
// функция предполагает, что размер
// массив n-2 и весь массив
// элементы различны

static void findTwoMissingNumbers(int []arr, 

                                  int n)

{

    // сумма 2 пропущенных чисел

    int sum = (n * (n + 1)) / 2 - 

              getSum(arr, n - 2);

  

    // Находим среднее из двух элементов

    int avg = (sum / 2);

  

    // Находим сумму элементов меньше

    // чем среднее значение (в среднем) и сумма

    // элементы больше среднего (в среднем)

    int sumSmallerHalf = 0, 

        sumGreaterHalf = 0;

    for (int i = 0; i < n - 2; i++)

    {

        if (arr[i] <= avg)

            sumSmallerHalf += arr[i];

        else

            sumGreaterHalf += arr[i];

    }

  

    Console.WriteLine("Two Missing "

                      "Numbers are ");

  

    // Первый (меньший) элемент =

    // (сумма натуральных чисел до

    // avg) - (сумма элементов массива

    // меньше или равно avg)

    int totalSmallerHalf = (avg * 

                           (avg + 1)) / 2;

    Console.WriteLine(totalSmallerHalf - 

                        sumSmallerHalf);

  

    // Первый (меньший) элемент =

    // (сумма натуральных чисел из

    // avg + 1 до n) - (сумма массива

    // элементы больше чем avg)

    Console.WriteLine(((n * (n + 1)) / 2 - 

                        totalSmallerHalf) - 

                        sumGreaterHalf);

}

  
// Код драйвера

static public void Main ()

{

    int []arr = {1, 3, 5, 6};

      

    // Диапазон чисел равен 2

    // плюс размер массива

    int n = 2 + arr.Length;

      

    findTwoMissingNumbers(arr, n);

}
}

  
// Этот код предоставлен ajit

PHP

<?php
// Программа PHP, чтобы найти 2 пропавших без вести
// Числа, использующие O (1) лишний пробел

  
// Возвращает сумму массива

function getSum($arr, $n)

{

    $sum = 0;

    for ($i = 0; $i < $n; $i++)

        $sum += $arr[$i];

    return $sum;

}

  
// Функция для поиска двух пропавших без вести
// числа в диапазоне [1, n]. Эта
// функция предполагает, что размер
// массив n-2 и весь массив
// элементы различны

function findTwoMissingNumbers($arr, $n)

{

    // сумма 2 пропущенных чисел

    $sum = ($n * ($n + 1)) /2 - 

            getSum($arr, $n - 2);

  

    // Находим среднее из двух элементов

    $avg = ($sum / 2);

  

    // Находим сумму элементов меньше

    // чем среднее значение (в среднем) и сумма

    // элементы больше среднего (в среднем)

    $sumSmallerHalf = 0;

    $sumGreaterHalf = 0;

    for ($i = 0; $i < $n - 2; $i++)

    {

        if ($arr[$i] <= $avg)

            $sumSmallerHalf += $arr[$i];

        else

            $sumGreaterHalf += $arr[$i];

    }

  

    echo "Two Missing Numbers are\n";

  

    // Первый (меньший) элемент =

    // (сумма натуральных чисел до avg) -

    // (сумма элементов массива меньше

    // чем или равно avg)

    $totalSmallerHalf = ($avg * ($avg + 1)) / 2;

    echo ($totalSmallerHalf -

          $sumSmallerHalf) , " ";

  

    // Первый (меньший) элемент =

    // (сумма натуральных чисел от avg +

    // от 1 до n) - (сумма элементов массива

    // больше, чем в среднем)

    echo ((($n * ($n + 1)) / 2 - $totalSmallerHalf) -

                                 $sumGreaterHalf);

}

  
// Код драйвера

$arr= array (1, 3, 5, 6);

  
// Диапазон чисел
// 2 плюс размер массива

$n = 2 + sizeof($arr);

  

findTwoMissingNumbers($arr, $n);

  
// Этот код предоставлен aj_36
?>


Выход :

Two Missing Numbers are
2 4

Примечание: могут быть проблемы переполнения в вышеупомянутом решении.

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

Найти два недостающих номера | Набор 2 (решение на основе XOR)

Эта статья предоставлена Чирагом Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Найти два недостающих номера | Набор 1 (Интересное решение с линейным временем)

0.00 (0%) 0 votes