Trying to put down a method, I think would work ( with a small running
example )
//! Assuming non--negative numbers and difference is MOD of difference
of numbers
Let array be A[1..n] //! e.g. { 11 , 6 , 17 , 9 ]
Start with pari ( A[1], A[2] ) and difference be D = | A[1] - A[2]
| /// A[1] = 11 , A[2] = 6 , D = 5
Now take A[3] , see if it lies b/w A[1] and A[2] //! A[3] = 17 ,
is it b/w { 11, 6} => NO
if NO , continue
else
check where left or right member of pair is closer to
it //! pair = (11,6) , next num = 9
new pair = (Left,A[3]) OR ( A[3],
right ) //! new pair = (11,9)
Time : O(n) as we are traveling array once
Space Coplexity : O(1) just need to store pair of numbers..
Thoughts ?
-Manish
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
