The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
310 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.5k points)
closed by | 310 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 (96.2k 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
@habibkhan can we do like this

We just find A[0] which will be first term of ap. Then we can find common difference  by subtracting a[0]by a[1] and a[1]and a[2] (for cross checking as a1 or a2 may be the elements we are seeking).we apply binary search and if a+(I+1-1)d is equal to a[I] we will go right and if it is lesser than a[I] we go left.
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.4k points)
edited by

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,831 questions
36,676 answers
90,578 comments
34,638 users