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

+1 vote

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 (59.6k 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 Jan 2017
  1. Debashish Deka

    7906 Points

  2. Habibkhan

    4736 Points

  3. Vijay Thakur

    4474 Points

  4. sudsho

    4318 Points

  5. saurabh rai

    4200 Points

  6. Arjun

    3638 Points

  7. Bikram

    3494 Points

  8. santhoshdevulapally

    3470 Points

  9. GateSet

    3228 Points

  10. Sushant Gokhale

    3116 Points

Monthly Topper: Rs. 500 gift card

18,944 questions
23,897 answers
52,113 comments
20,213 users