Find the missing number in unordered Arithmetic Progression

Given an unsortedarray 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 useBinary Search. Sort the given array then the array will arranged in sorted order of AP series, we can apply Binary Search (as inthis article) as described below:

  1. 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 .
  2. 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.
  3. Else the element lies in the left side of the middle element.

Below is the implementation of the above approach:

filter_none

edit

close

play_arrow

link

brightness_4

code

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the missing element
int 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 series
int 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 Code
int 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;
}

chevron_right

filter_none

Output:

Output:

Time Complexity:O(N*log 2 N)

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:

  1. Find the maximum and minimum elements from the given array.
  2. Find the common difference as:

  3. Calculate xor for all elements in the array.
  4. 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:

filter_none

edit

close

play_arrow

link

brightness_4

code

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to get the missing element
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
int 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;
}

chevron_right

filter_none

Output:

Time complexity: O(N)

Auxiliary Space: O(1)

My Personal Notes arrow_drop_up

  
 

Recommended Posts:

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章