# 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

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 + 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) / 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);`
` `
`  ` `// 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

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;`
` `
`  ` `// For minimum Element in the array`
`  ` `int` `min_ele = arr;`
` `
`  ` `// 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);`
` `
`  ` `// 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