Hi,
I hav a problem at hand...plz help out. I am not allowd to compuet o(n)...i need to compute the algorithm in O(log n).
Suppose there is some number N, and there are 7 elements in another array. Each element in the array is given another special number(one number per element),say K Then we have to form the array by adding the first given value of N (-100) to the special 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) + special 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 check 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? and also going by this logic, the array B will always be in ascending order and sorted.
A binary search is what i am thinking of but i am confused of the algorithm.
At any point of time after i check if the middle element is > array.size() . all the index values > array size are void and they can be discarded...i can infer this much. but and then what?
for example array like {1,2,8,16,23}
i ll chk if the middle value 8>array size //5 and since it is greater, i know that the upper half cannot be the answer. but what from ther on?
Given this, is it now possible to compute in O(log n) ? I am supposed to compute the algorithm only in O(log n)...
Plz help out...
Thank you