Given an unsorted array arr[] of N integers that are in Arithmetic Progression, the task is to print the missing element from the given series.
Examples:
Input: arr[] = {12, 3, 6, 15, 18}
Output: 9
Explanation:
The elements given in order are: 3, 6, 12, 15, 18.
Hence missing element is 9.Input: arr[] = {2, 8, 6, 10}
Output: 4
Explanation:
The elements given in order are: 2, 6, 8, 10.
Hence missing element is 4.
Naive Approach: The idea is to use Binary Search. Sort the given array then the array will arranged in sorted order of AP series, we can apply Binary Search (as in this article) as described below:
- Find the middle element and check if the difference between the middle element and the next element to the middle element is equal to common difference or not, if not then the missing element lies between mid and mid + 1.
- If the middle element is equal to (N/2)th term in the given Arithmetic Series, then the missing element lies in the right side of the middle element.
- Else the element lies in the left side of the middle element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the missing elementint findMissing(int arr[], int left, int right, int diff){ // Fix left and right boundary // for binary search if (right <= left) return INT_MAX; // Find index of middle element int mid = left + (right - left) / 2; // Check if the element just after // the middle element is missing if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); // Check if the element just // before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); // Check if the elements till mid // follow the AP, then recur // for right half if (arr[mid] == arr[0] + mid * diff) return findMissing(arr, mid + 1, right, diff); // Else recur for left half return findMissing(arr, left, mid - 1, diff);}// Function to find the missing// element in AP seriesint missingElement(int arr[], int n){ // Sort the array arr[] sort(arr, arr + n); // Calculate Common Difference int diff = (arr[n - 1] - arr[0]) / n; // Binary search for the missing return findMissing(arr, 0, n - 1, diff);}// Driver Codeint main(){ // Given array arr[] int arr[] = { 2, 8, 6, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << missingElement(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays; class GFG{ // Function to find the missing elementstatic int findMissing(int arr[], int left, int right, int diff){ // Fix left and right boundary // for binary search if (right <= left) return 0; // Find index of middle element int mid = left + (right - left) / 2; // Check if the element just after // the middle element is missing if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); // Check if the element just // before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); // Check if the elements till mid // follow the AP, then recur // for right half if (arr[mid] == arr[0] + mid * diff) return findMissing(arr, mid + 1, right, diff); // Else recur for left half return findMissing(arr, left, mid - 1, diff);}// Function to find the missing// element in AP seriesstatic int missingElement(int arr[], int n){ // Sort the array arr[] Arrays.sort(arr); // Calculate Common Difference int diff = (arr[n - 1] - arr[0]) / n; // Binary search for the missing return findMissing(arr, 0, n - 1, diff);}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = new int[]{ 2, 8, 6, 10 }; int n = arr.length; // Function Call System.out.println(missingElement(arr, n));}}// This code is contributed by rock_cool |
Python3
# Python3 program for the above approachimport sys# Function to find the missing elementdef findMissing(arr, left, right, diff): # Fix left and right boundary # for binary search if (right <= left): return sys.maxsize # Find index of middle element mid = left + (right - left) // 2 # Check if the element just after # the middle element is missing if (arr[mid + 1] - arr[mid] != diff): return (arr[mid] + diff) # Check if the element just # before mid is missing if (mid > 0 and arr[mid] - arr[mid - 1] != diff): return (arr[mid - 1] + diff) # Check if the elements till mid # follow the AP, then recur # for right half if (arr[mid] == arr[0] + mid * diff): return findMissing(arr, mid + 1, right, diff) # Else recur for left half return findMissing(arr, left, mid - 1, diff)# Function to find the missing# element in AP seriesdef missingElement(arr, n): # Sort the array arr[] arr.sort() # Calculate Common Difference diff = (arr[n - 1] - arr[0]) // n # Binary search for the missing return findMissing(arr, 0, n - 1, diff)# Driver Code# Given array arr[]arr = [ 2, 8, 6, 10 ]n = len(arr)# Function callprint(missingElement(arr, n))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approach using System;class GFG{ // Function to find the missing element static int findMissing(int []arr, int left, int right, int diff) { // Fix left and right boundary // for binary search if (right <= left) return 0; // Find index of middle element int mid = left + (right - left) / 2; // Check if the element just after // the middle element is missing if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); // Check if the element just // before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); // Check if the elements till mid // follow the AP, then recur // for right half if (arr[mid] == arr[0] + mid * diff) return findMissing(arr, mid + 1, right, diff); // Else recur for left half return findMissing(arr, left, mid - 1, diff); } // Function to find the missing // element in AP series static int missingElement(int []arr, int n) { // Sort the array []arr Array.Sort(arr); // Calculate Common Difference int diff = (arr[n - 1] - arr[0]) / n; // Binary search for the missing return findMissing(arr, 0, n - 1, diff); } // Driver Code public static void Main(String[] args) { // Given array []arr int []arr = new int[]{ 2, 8, 6, 10 }; int n = arr.Length; // Function Call Console.WriteLine(missingElement(arr, n)); } } // This code is contributed by Rohit_ranjan |
Javascript
<script>// Javascript program for the above approach// Function to find the missing elementfunction findMissing(arr, left, right, diff){ // Fix left and right boundary // for binary search if (right <= left) return 0; // Find index of middle element let mid = left + parseInt((right - left) / 2, 10); // Check if the element just after // the middle element is missing if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); // Check if the element just // before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); // Check if the elements till mid // follow the AP, then recur // for right half if (arr[mid] == arr[0] + mid * diff) return findMissing(arr, mid + 1, right, diff); // Else recur for left half return findMissing(arr, left, mid - 1, diff);}// Function to find the missing// element in AP seriesfunction missingElement(arr, n){ // Sort the array []arr arr.sort(function(a, b){return a - b}); // Calculate Common Difference let diff = parseInt((arr[n - 1] - arr[0]) / n, 10); // Binary search for the missing return findMissing(arr, 0, n - 1, diff);}// Driver code// Given array []arrlet arr = [ 2, 8, 6, 10 ];let n = arr.length;// Function Calldocument.write(missingElement(arr, n));// This code is contributed by rameshtravel07</script> |
Output:
4
Time Complexity: O(N*log2N)
Auxiliary Space: O(1) as it is using constant space
Efficient Approach: To optimize the above method we will use the following properties of XOR that is a ^ a = 0, hence, (a ^ b ^ c) ^ (a ^ c) = b. Below are the steps:
- Find the maximum and minimum elements from the given array.
- Find the common difference as:
- Calculate xor for all elements in the array.
- Perform xor with all the elements of the actual series to find the resultant value is the missing element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to get the missing elementint missingElement(int arr[], int n){ // For maximum Element in the array int max_ele = arr[0]; // For minimum Element in the array int min_ele = arr[0]; // For xor of all elements int x = 0; // Common difference of AP series int d; // find maximum and minimum element for (int i = 0; i < n; i++) { if (arr[i] > max_ele) max_ele = arr[i]; if (arr[i] < min_ele) min_ele = arr[i]; } // Calculating common difference d = (max_ele - min_ele) / n; // Calculate the XOR of all elements for (int i = 0; i < n; i++) { x = x ^ arr[i]; } // Perform XOR with actual AP series // resultant x will be the ans for (int i = 0; i <= n; i++) { x = x ^ (min_ele + (i * d)); } // Return the missing element return x;}// Driver Codeint main(){ // Given array int arr[] = { 12, 3, 6, 15, 18 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call int element = missingElement(arr, n); // Print the missing element cout << element;} |
Java
// Java program for the above approachclass GFG{ // Function to get the missing elementstatic int missingElement(int arr[], int n){ // For maximum Element in the array int max_ele = arr[0]; // For minimum Element in the array int min_ele = arr[0]; // For xor of all elements int x = 0; // Common difference of AP series int d; // find maximum and minimum element for(int i = 0; i < n; i++) { if (arr[i] > max_ele) max_ele = arr[i]; if (arr[i] < min_ele) min_ele = arr[i]; } // Calculating common difference d = (max_ele - min_ele) / n; // Calculate the XOR of all elements for(int i = 0; i < n; i++) { x = x ^ arr[i]; } // Perform XOR with actual AP series // resultant x will be the ans for(int i = 0; i <= n; i++) { x = x ^ (min_ele + (i * d)); } // Return the missing element return x;}// Driver code public static void main(String[] args) { // Given array int arr[] = new int[]{ 12, 3, 6, 15, 18 }; int n = arr.length; // Function Call int element = missingElement(arr, n); // Print the missing element System.out.print(element); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach# Function to get the missing elementdef missingElement(arr, n): # For maximum element in the array max_ele = arr[0] # For minimum Element in the array min_ele = arr[0] # For xor of all elements x = 0 # Common difference of AP series d = 0 # Find maximum and minimum element for i in range(n): if (arr[i] > max_ele): max_ele = arr[i] if (arr[i] < min_ele): min_ele = arr[i] # Calculating common difference d = (max_ele - min_ele) // n # Calculate the XOR of all elements for i in range(n): x = x ^ arr[i] # Perform XOR with actual AP series # resultant x will be the ans for i in range(n + 1): x = x ^ (min_ele + (i * d)) # Return the missing element return x# Driver Codeif __name__ == '__main__': # Given array arr = [ 12, 3, 6, 15, 18 ] n = len(arr) # Function Call element = missingElement(arr, n) # Print the missing element print(element)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to get the missing elementstatic int missingElement(int[] arr, int n){ // For maximum Element in the array int max_ele = arr[0]; // For minimum Element in the array int min_ele = arr[0]; // For xor of all elements int x = 0; // Common difference of AP series int d; // find maximum and minimum element for(int i = 0; i < n; i++) { if (arr[i] > max_ele) max_ele = arr[i]; if (arr[i] < min_ele) min_ele = arr[i]; } // Calculating common difference d = (max_ele - min_ele) / n; // Calculate the XOR of all elements for(int i = 0; i < n; i++) { x = x ^ arr[i]; } // Perform XOR with actual AP series // resultant x will be the ans for(int i = 0; i <= n; i++) { x = x ^ (min_ele + (i * d)); } // Return the missing element return x;}// Driver code public static void Main() { // Given array int[] arr = new int[]{ 12, 3, 6, 15, 18 }; int n = arr.Length; // Function Call int element = missingElement(arr, n); // Print the missing element Console.Write(element); } }// This code is contributed by Ritik Bansal |
Javascript
<script> // Javascript program for the above approach // Function to get the missing element function missingElement(arr, n) { // For maximum Element in the array let max_ele = arr[0]; // For minimum Element in the array let min_ele = arr[0]; // For xor of all elements let x = 0; // Common difference of AP series let d; // find maximum and minimum element for (let i = 0; i < n; i++) { if (arr[i] > max_ele) max_ele = arr[i]; if (arr[i] < min_ele) min_ele = arr[i]; } // Calculating common difference d = parseInt((max_ele - min_ele) / n, 10); // Calculate the XOR of all elements for (let i = 0; i < n; i++) { x = x ^ arr[i]; } // Perform XOR with actual AP series // resultant x will be the ans for (let i = 0; i <= n; i++) { x = x ^ (min_ele + (i * d)); } // Return the missing element return x; } // Given array let arr = [ 12, 3, 6, 15, 18 ]; let n = arr.length; // Function Call let element = missingElement(arr, n); // Print the missing element document.write(element); </script> |
Output:
9
Time complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
