Найти недостающий элемент в отсортированном массиве последовательных чисел

Опубликовано: 14 Января, 2022

Дан массив arr [] из n различных целых чисел. Элементы размещаются последовательно в порядке возрастания, при этом один элемент отсутствует. Задача - найти недостающий элемент.
Примеры:

Input: arr[] = {1, 2, 4, 5, 6, 7, 8, 9}
Output: 3
Input: arr[] = {-4, -3, -1, 0, 1, 2}
Output: -2
Input: arr[] = {1, 2, 3, 4}
Output: -1
No element is missing.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Принципы:

Look for inconsistency: Ideally, the difference between any element and its index must be arr[0] for every element.
Example,
A[] = {1, 2, 3, 4, 5} -> Consistent
B[] = {101, 102, 103, 104} -> Consistent
C[] = {1, 2, 4, 5, 6} -> Inconsistent as C[2] – 2 != C[0] i.e. 4 – 2 != 1

Finding inconsistency helps to scan only half of the array each time in O(logN).

Алгоритм

Find middle element and check if it’s consistent.
If middle element is consistent, then check if the difference between middle element and its next element is greater than 1 i.e. check if arr[mid + 1] – arr[mid] > 1
If yes, then arr[mid] + 1 is the missing element.
If not, then we have to scan the right half array from the middle element and jump to step-1.
If middle element is inconsistent, then check if the difference between middle element and its previous element is greater than 1 i.e. check if arr[mid] – arr[mid – 1] > 1
If yes, then arr[mid] – 1 is the missing element.
If not, then we have to scan the left half array from the middle element and jump to step-1.

Below is the implementation of the above approach:

C++

// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the missing element
int findMissing(int arr[], int n)
{
 
    int l = 0, h = n - 1;
    int mid;
 
    while (h > l)
    {
 
        mid = l + (h - l) / 2;
 
        // Check if middle element is consistent
        if (arr[mid] - mid == arr[0])
        {
 
            // No inconsistency till middle elements
            // When missing element is just after
            // the middle element
            if (arr[mid + 1] - arr[mid] > 1)
                return arr[mid] + 1;
            else
            {
                // Move right
                l = mid + 1;
            }
        }
        else
        {
 
            // Inconsistency found
            // When missing element is just before
            // the middle element
            if (arr[mid] - arr[mid - 1] > 1)
                return arr[mid] - 1;
            else
            {
                // Move left
                h = mid - 1;
            }
        }
    }
 
    // No missing element found
    return -1;
}
 
// Driver code
int main()
{
    int arr[] = { -9, -8, -7, -5, -4, -3, -2, -1, 0 };
    int n = sizeof(arr)/sizeof(arr[0]);
 
    cout << (findMissing(arr, n));
}
     
// This code iscontributed by
// Surendra_Gangwar

Java

// Java implementation of the approach
class GFG {
 
    // Function to return the missing element
    public static int findMissing(int arr[], int n)
    {
 
        int l = 0, h = n - 1;
        int mid;
 
        while (h > l) {
 
            mid = l + (h - l) / 2;
 
            // Check if middle element is consistent
            if (arr[mid] - mid == arr[0]) {
 
                // No inconsistency till middle elements
                // When missing element is just after
                // the middle element
                if (arr[mid + 1] - arr[mid] > 1)
                    return arr[mid] + 1;
                else {
 
                    // Move right
                    l = mid + 1;
                }
            }
            else {
 
                // Inconsistency found
                // When missing element is just before
                // the middle element
                if (arr[mid] - arr[mid - 1] > 1)
                    return arr[mid] - 1;
                else {
 
                    // Move left
                    h = mid - 1;
                }
            }
        }
 
        // No missing element found
        return -1;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int arr[] = { -9, -8, -7, -5, -4, -3, -2, -1, 0 };
        int n = arr.length;
 
        System.out.print(findMissing(arr, n));
    }
}

Python3

# Python implementation of the approach
 
# Function to return the missing element
def findMissing(arr, n):
 
    l, h = 0, n - 1
    mid = 0
 
    while (h > l):
 
        mid = l + (h - l) // 2
 
        # Check if middle element is consistent
        if (arr[mid] - mid == arr[0]):
 
            # No inconsistency till middle elements
            # When missing element is just after
            # the middle element
            if (arr[mid + 1] - arr[mid] > 1):
                return arr[mid] + 1
            else:
 
                # Move right
                l = mid + 1
             
        else:
 
            # Inconsistency found
            # When missing element is just before
            # the middle element
            if (arr[mid] - arr[mid - 1] > 1):
                return arr[mid] - 1
            else:
 
                # Move left
                h = mid - 1
             
    # No missing element found
    return -1
 
# Driver code
arr = [-9, -8, -7, -5, -4, -3, -2, -1, 0 ]
n = len(arr)
 
print(findMissing(arr, n))
 
# This code is contributed
# by mohit kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the missing element
    public static int findMissing(int[] arr, int n)
    {
 
        int l = 0, h = n - 1;
        int mid;
 
        while (h > l)
        {
 
            mid = l + (h - l) / 2;
 
            // Check if middle element is consistent
            if (arr[mid] - mid == arr[0])
            {
 
                // No inconsistency till middle elements
                // When missing element is just after
                // the middle element
                if (arr[mid + 1] - arr[mid] > 1)
                    return arr[mid] + 1;
                else
                {
 
                    // Move right
                    l = mid + 1;
                }
            }
            else
            {
 
                // Inconsistency found
                // When missing element is just before
                // the middle element
                if (arr[mid] - arr[mid - 1] > 1)
                    return arr[mid] - 1;
                else
                {
 
                    // Move left
                    h = mid - 1;
                }
            }
        }
 
        // No missing element found
        return -1;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { -9, -8, -7, -5, -4, -3, -2, -1, 0 };
        int n = arr.Length;
 
        Console.WriteLine(findMissing(arr, n));
    }
}
 
// This code is contributed by Code_Mech

PHP

<?php
// PHP implementation of the approach
 
// Function to return the missing element
function findMissing($arr, $n)
{
    $l = 0; $h = $n - 1;
 
    while ($h > $l)
    {
 
        $mid = floor($l + ($h - $l) / 2);
 
        // Check if middle element is consistent
        if ($arr[$mid] - $mid == $arr[0])
        {
 
            // No inconsistency till middle elements
            // When missing element is just after
            // the middle element
            if ($arr[$mid + 1] - $arr[$mid] > 1)
                return $arr[$mid] + 1;
            else
            {
 
                // Move right
                $l = $mid + 1;
            }
        }
        else
        {
 
            // Inconsistency found
            // When missing element is just before
            // the middle element
            if ($arr[$mid] - $arr[$mid - 1] > 1)
                return $arr[$mid] - 1;
            else
            {
 
                // Move left
                $h = $mid - 1;
            }
        }
    }
 
    // No missing element found
    return -1;
}
 
// Driver code
$arr = array( -9, -8, -7, -5, -
               4, -3, -2, -1, 0 );
$n = count($arr);
 
echo findMissing($arr, $n);
 
// This code is contributed by Ryuga
?>

Javascript

<script>
// JavaScript implementation of the approach
 
// Function to return the missing element
function findMissing(arr, n)
{
 
    let l = 0, h = n - 1;
    let mid;
 
    while (h > l)
    {
 
        mid = l + Math.floor((h - l) / 2);
 
        // Check if middle element is consistent
        if (arr[mid] - mid == arr[0])
        {
 
            // No inconsistency till middle elements
            // When missing element is just after
            // the middle element
            if (arr[mid + 1] - arr[mid] > 1)
                return arr[mid] + 1;
            else
            {
                // Move right
                l = mid + 1;
            }
        }
        else
        {
 
            // Inconsistency found
            // When missing element is just before
            // the middle element
            if (arr[mid] - arr[mid - 1] > 1)
                return arr[mid] - 1;
            else
            {
                // Move left
                h = mid - 1;
            }
        }
    }
 
    // No missing element found
    return -1;
}
 
// Driver code
    let arr = [ -9, -8, -7, -5, -4, -3, -2, -1, 0 ];
    let n = arr.length;
 
    document.write(findMissing(arr, n));
     
 
 
 
// This code is contributed by Surbhi Tyagi.
</script>

Output:

-6

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Найти недостающий элемент в отсортированном массиве последовательных чисел

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ