GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
245 views
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?
closed as a duplicate of: ARRAYS
asked in Algorithms by Boss (6.3k points)  
closed by | 245 views

@rameshbabu dont show ur caliber by downvoting..If u have caliber , argue properly..What is wrong in my answer..And by the way I have used a reference which is valid :

http://www.geeksforgeeks.org/find-missing-number-arithmetic-progression/

 

This attitude of yours simply shows ur lack of interest in discussion..Be careful from next time from doing so...Else I will report to moderators..

And by the way ur answer is not also appropriate..I can also mark it like u have done..But I m not like u.
He never ment to offect you, please don't get offended

I did not find your alogorithm take care of binary search condition
Now u can find from the link I mentioned in comment and remove downvote from my answer..And who is "he" ..U urself have dont this thing..

And keep in mind what I have said in future..

If u downvote , u should have valid point right..

And it is not that I have written any unjustified or silly answer..

2 Answers

+3 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..

answered by Veteran (76.9k points)  
just checking difference middle term and term next to it,

we will not be able to make decision to go left or right

lets have an example

1,2,4,5,6,7,8

middle term = 5 ,

next = 6

difference = 1 = diff of AP

just by this info we are unable to take left/ right move
But is 5 the (n/2)th term of AP??It is not..

And check the reference that I have given..It is fine..No flaw in that..
ok accepted
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)

answered by Loyal (3.3k points)  
edited by

Related questions



Top Users Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1756 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,060 questions
33,669 answers
79,747 comments
31,080 users