CODEWITHSUNDEEP
arraysalgorithmdata-structures
brainydexter
brainydexter

Reputation: 20346

Find an element in array where each element is one more or one less than its preceding element

Given an array , each element is one more or one less than its preceding element .find an element in it.(better than O(n) approach)

I have a solution for this but I have no way to tell formally if it is the correct solution:

Let us assume we have to find n.

Upvotes: 3

Views: 929

Answers (2)

DevCoder
DevCoder

Reputation: 536

Prepocessing can help here. Find Minimum and Maximum element of array in O(n) time complexity. If element to be queried is between Minimum and Maximum of array, then that element is present in array, else that element is not present in that array.So any query will take O(1) time. If that array is queried multiple times, than amortized time complexity will be lesser that O(n).

Upvotes: 0

Bernhard Barker
Bernhard Barker

Reputation: 55589

Yes, your approach will work.

If you can only increase / decrease by one at each following index, there's no way a value at an index closer than d could be a distance d from the current value. So there's no way you can skip over the target value. And, unless the value is found, the distance will always be greater than 0, thus you'll keep moving right. Thus, if the value exists, you'll find it.

No, you can't do better than O(n) in the worst case.

Consider an array 1,2,1,2,1,2,1,2,1,2,1,2 and you're looking for 0. Any of the 2's can be changed to a 0 without having to change any of the other values, thus we have to look at all the 2's and there are n/2 = O(n) 2's.

Upvotes: 8

Related Questions