Find missing element in a sorted array of consecutive numbers
Given an array arr[] of n distinct integers. Elements are placed sequentially in ascending order with one element missing. The task is to find the missing element.
Examples:
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.
Principles:
- 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).
Algorithm
- 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
Time Complexity : O(log(N) )
Auxiliary Space: O(1)
Contact Us