GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
183 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 (5.9k points)  
closed by | 183 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 (67k 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.2k points)  
edited by

Related questions



Top Users Jul 2017
  1. Bikram

    5784 Points

  2. manu00x

    3602 Points

  3. Arjun

    1988 Points

  4. Debashish Deka

    1924 Points

  5. joshi_nitish

    1908 Points

  6. pawan kumarln

    1680 Points

  7. Tesla!

    1426 Points

  8. Hemant Parihar

    1334 Points

  9. Shubhanshu

    1180 Points

  10. Arnab Bhadra

    1124 Points


24,169 questions
31,187 answers
71,039 comments
29,512 users