GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
135 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.7k points)  
closed by | 135 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

+2 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 (65.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.1k points)  
edited by

Related questions



Top Users Apr 2017
  1. akash.dinkar12

    3514 Points

  2. Divya Bharti

    2546 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,042 answers
63,233 comments
24,135 users