we can use a modified binary search to find the element.
whenever u calculate a new lower and upper boundary you can move them
forward and backward respectively so that both point to a index which
contains a valid number.But still this wont give O(n).
do we have any memory constraints?
do we have
I dont think its possible in O(n), as invalid is still a value. i.e u dont
know if a
number is valid or invalid unless u read the value. Unless there is some
pattern in distribution of
those n valid numbers, u wont know which numbers will be invalid before hand
to skip reading them.
On 5/6/07, Nis
Sorry it is some not sum...
Yes ,actually the array is infinite,has some n elements in sorted order ,may
not be continous and if the array has invalid numbers it has -1 in
it.Nowthe task is to find a given valid
number.Pls help me out now?
On 5/7/07, Nisha Subramanian <[EMAIL PROTECTED]> wrote
Yes ,actually the array is infinite,has sum n elements in sorted order ,may
not be continous and if the array has invalid numbers it has -1 in
it.Nowthe task is to find a given valid
number.Pls help me out now?
On 5/7/07, Arun <[EMAIL PROTECTED]> wrote:
>
> BiGYan,
> I think ur solution will not
hello dear please think about tis problem:
Farmer John wants to place a big square barn on his square farm. he hates to
cut down trees on his farm and wants to find a location for his barn that
enables him to build it only on land that is already clear of trees.For our
purposes, his land is divid
BiGYan,
I think ur solution will not work as u r assuming the the "valid" numbers
are stored contigously and n>inc
> while ( arr[i].val<=s )
>i+=inc;
I think the question can be rephrased as a very large array of size N,
has n valid numbers (n< wrote:
>
>
> Infinite Array ?
> Infinite Array i
Infinite Array ?
Infinite Array in sorted order ?
Let's say we have an infinite array where each of the elements have a
number (according to which it is sorted) and a valid/invalid bit for
storing the validity.
s - number we are searching for
arr[] - the infinite array
inc = 100;// this is
