O(log n) algorithm help !!!!!!

[itseeker87]

Hi,

I have a problem at hand and i kinda need a head start in the same.

I have an array with some values inside and basically i need to check if the array (index value+1) == the actual value in that index and if so, i need to increase a counter.

int a[] = {-1, 0, 2, 4, 5, 6, 7}

and the result shud be 4 for this because ther are 4 elements in this array which satisfy the condition... as, starting from index a[3] till a[6]....the value of index is equal to (index+1)

like a[3] = 4
a[4] = 5
a[5] = 6
a[6] = 7

but the catch is to do it in O(log N)...and not o(n).....can someone plz gimme a head start into solving this problem??

thnx in advance...plz reply soon...its urgent :) thnk yu

[Eranga]

Do you want to increase the value after condition is satisfied?

[Norm]

do it in O(log N)...and not o(n).

Having been away from the textbooks for years, can you explain the difference between those two?

[itseeker87]

Do you want to increase the value after condition is satisfied?

There is no need for increase of any value other than a counter which keeps track of the number hits(condition satisfied)...

So,is there a solution in O(log n) for this problem .... i am guessing that it is a possible for sure as this is part of a project work i am involved in and the specs required an O(log n) solution for this very same problem...

is it possible??

thnx...

[itseeker87]

Having been away from the textbooks for years, can you explain the difference between those two?

O(n) is linear...for example...finding an item in an unsorted list...

O(log n) logarithmic like Finding an item in a sorted array with a binary search...

the the sort range half themselves over every iteration, so to speak in the case of O(log n)....

so given that...is the problem i posted solvable in O(log n) ??

thnx...

[itseeker87]

Hi,

sorry for the confusion earlier....

ONE important point to note is that the array is alwayz assumed SORTED...in ascending order....

This being the case... is it possible to reach (log n)... i do understand that there is a need to go thru the entire array to arrive at a result(thats the obvious algo which i d think of)....but the specs given for this assignment is that it has to be done in O(log n)....

let me give a more clearer view to the problem, i hav not been explicit , i am sorry...

Suppose there is some number N, and there are 7 elements in another array. Each element in the array is given another spl number(one number per element)....say K ...then we hav to form the array by adding the first given value of N (-100) to the spl number K for first array(A) element. The resultant value is the first value of our input array(B). and this value now replaces for the new N. The 2nd element of the input array(B) = first value of array(B) + spl number K for 2nd element of array(A) and so on...

eg. N = -100 (intial value)
Array A: {99, 1, 2, 2, 1, 1, 1} [differnt K values]

then array B becomes

{ -1, 0, 2, 4, 5, 6, 7}.... [explanation -100 + 99 = -1 ---> -1 + 1 = 0---> 0+2= 2---->2+2 =4 ---->4+1=5---->5+1=6--->6+1=7 ]

it is this array that we have to chk for the condition i posted earlier... (index+1 = value of index)

At any point of time we can find the array A values for each array B value by subtracting the 2 adjacent index values...i was able to infer this now...does this help with a solution?

Given this... is it now possible to compute in O(log n) ???

[Norm]

How does your question relate to Java?
It looks like you are looking for an algorithm.
When you get the algorithm, post it and we'll help you write it in java.

[itseeker87]

yes...but i am implementing the algorithm in java ...

help please.

[Norm]

See also the other post at:
http://www.codeguru.com/forum/showthread.php?t=460763