Redirected
retagged by
2,630 views
3 votes
3 votes
Consider an array containing ‘n’ elements. The elements present in an array are in arithmetic progression, but one element is missing in that order. What is the time complexity to find the position of the missing element using divide and conquer?
retagged by

4 Answers

Best answer
3 votes
3 votes
Find sum of elemets of the array, $AS=\sum_{i=1}^{n}A[i]$. Take $\theta(n)$

Then sum of AP is $S = \frac{n}{2}[2a + (n - 1)d]$ Take $\theta(1)$

$x=S-AS$ will the missing element.

//Find the position of next element (x+d) in array, using binary search

$position=Binary\_Search(A,x+d)-1$ Take $O(\log n)$

$T(n)=\theta(n)+O(\log n)=O(n)$
selected by
5 votes
5 votes

Simple Solution is to linearly traverse the array and find the missing number. Time complexity of this solution is O(n).

We can solve this problem in O(Logn) time using Binary search modification..

 The idea is to go to the middle element. Check if the difference between middle and next to middle is equal to diff or not, if not then the missing element lies between mid and mid+1. If the middle element is equal to n/2th term in Arithmetic Series (Let n be the number of elements in input array), then missing element lies in right half. Else element lies in left half.

Hope this helps..

2 votes
2 votes

$O(\log n)$ solution.

I think this can be solved as follows:

  1. Find the difference of AP by finding the difference of any three consecutive pairs and pick the difference which occurs atleast twice. Let it be $d$.
  2. Now find whether the $array[\frac{n}{2}]$  is the $(\frac{n}{2})^{th}$ element of the AP using the nth term formula i.e. $a_{n}=a+(n-1)d$
  3. If yes then the missing term lies on the right side, hence call the function recursively on right side indices.
  4. Else, the missing term lies on the left side or can be this middle term itself, hence call the function recursively on left side indices.

The recurrence relation for the above logic:

$T(n)=T(\frac{n}{2})+1$

Hence, $O(\log n)$ time complexity.

0 votes
0 votes

you can find the nth term of AP by formula as

( nth term of AP = first element + n * diff )

You also know how logic of binary search works

if middle element of series equals to nth term of series

    {  you can conclude series is progressing correctly

        in coerrect element could be on right side }

else

   { goto left }

this will will take O (log( N )) time,

which is less than linear search time which is O(N)

edited by

Related questions

4 votes
4 votes
1 answer
1
Aghori asked Nov 5, 2017
1,162 views
There are two sorted list each of length $n$. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons require...
14 votes
14 votes
4 answers
2
Arjun asked Feb 18, 2021
11,754 views
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?$\Theta ( \sqrt{n})$$\Theta (\log _2(n))$$\Theta...
0 votes
0 votes
1 answer
3
Sabir Khan asked Aug 8, 2018
1,056 views
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)