@Dave Thanks for pointing that out.
But I still can't get what if elem is on first element or it is not present
in the array? How is your code going to handle that situation?
@Atul, Well yes, In the given question, the number of iterations were 2n.
Which I have reduced to n+n/2.
On Tue, Oct 2, 2012 at 11:13 PM, atul anand <atul.87fri...@gmail.com> wrote:
> @umer : how no. of comparison are reduced to half by moving both
> sides....you have 2 if condition inside, so you are making 2
> comparisons at each iteration + n/2 comparison for while loop so
> number of comparisons are n+n/2
>
> On 10/2/12, Umer Farooq <the.um...@gmail.com> wrote:
> > why don't we try it from both ends ... something like this:
> >
> > int i = 0; j = size-1;
> >
> > while (i != j)
> > {
> > if (arr[i] == elem)
> > return arr[i];
> > if (arr[j] == elem)
> > return arr[j];
> > }
> >
> > this way, we have eliminated half of the comparisons in for loop? What do
> > you guys say?
> >
> > On Tue, Oct 2, 2012 at 12:18 PM, rafi <rafiwie...@gmail.com> wrote:
> >
> >> Vikas is right!
> >> while (n) is equal to (while n!=0)
> >> you have 2n compares!
> >>
> >> בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
> >>
> >>> still there is no improvement, compiler will generate the code to
> >>> compare
> >>> with zero here. what you have accomplished is , hide it from human eyes
> >>>
> >>> On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
> >>>>
> >>>> @atul:
> >>>> still it won't compare 0 th element. Slight modification in your code:
> >>>>
> >>>> n=*sizeof(arr)*;
> >>>> do
> >>>> {
> >>>> if(elem==arr[*--n*])
> >>>> print found;
> >>>>
> >>>> }while(n);
> >>>>
> >>>> On Mon, Oct 1, 2012 at 9:50 AM, atul anand <atul.8...@gmail.com>
> wrote:
> >>>>
> >>>>> yes, but there no need of checking outside the loop
> >>>>>
> >>>>> n=sizeof(arr)-1;
> >>>>> do
> >>>>> {
> >>>>> if(elem==arr[n])
> >>>>> print found;
> >>>>> n--;
> >>>>>
> >>>>> }while(n);
> >>>>>
> >>>>>
> >>>>>
> >>>>> On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
> >>>>> <algorit...@gmail.com>wrote:
> >>>>>
> >>>>>> @atul: keep one more checking outside loop for element at 0 th
> index.
> >>>>>> Because when n = 0 the your loop come out from the loop without
> >>>>>> comparing
> >>>>>> it.
> >>>>>>
> >>>>>>
> >>>>>> On Mon, Oct 1, 2012 at 8:55 AM, atul anand
> >>>>>> <atul.8...@gmail.com>wrote:
> >>>>>>
> >>>>>>> n=sizeof(arr);
> >>>>>>> n--;
> >>>>>>>
> >>>>>>> while(n)
> >>>>>>> {
> >>>>>>> if(elem=arr[n])
> >>>>>>> print found;
> >>>>>>>
> >>>>>>> n--;
> >>>>>>>
> >>>>>>> }
> >>>>>>>
> >>>>>>> On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר <rafiw...@gmail.com>
> >>>>>>> wrote:
> >>>>>>>
> >>>>>>>> Hi
> >>>>>>>> i was in an interview and was given a simple function
> >>>>>>>> int arrExsits(int* arr,int size,int elem){
> >>>>>>>> for (int i=0;i<size;++i)
> >>>>>>>> if(elem==arr[i])
> >>>>>>>> return i;
> >>>>>>>> return -1;
> >>>>>>>> }
> >>>>>>>> this function does 2n compares
> >>>>>>>> n- the if statment
> >>>>>>>> n-check that i is smaller then size
> >>>>>>>> i was suppose to give an optimal (less compares) solution so i
> gave
> >>>>>>>>
> >>>>>>>> int arrExsits(int* arr,int size,int elem){
> >>>>>>>> if (arr[size-1]==elem)
> >>>>>>>> return size-1;
> >>>>>>>> arr[size-1]=elem]
> >>>>>>>> for (int i=0;;++i)
> >>>>>>>> if(elem==arr[i]){
> >>>>>>>> if (i!=size-1)
> >>>>>>>> return i;
> >>>>>>>> return -1;
> >>>>>>>> }
> >>>>>>>> this solution works and it has n+2 compares the first one another
> n
> >>>>>>>> and the second inner if.
> >>>>>>>> they told me it's good (and I've passed) but they told just for my
> >>>>>>>> knowledge that there is a better N compare solution.
> >>>>>>>> I've searched the web but couldn't find it.
> >>>>>>>> anybody knows?
> >>>>>>>> Thanks
> >>>>>>>>
> >>>>>>>> --
> >>>>>>>> You received this message because you are subscribed to the Google
> >>>>>>>> Groups "Algorithm Geeks" group.
> >>>>>>>> To post to this group, send email to algo...@googlegroups.com.
> >>>>>>>> To unsubscribe from this group, send email to
> >>>>>>>> algogeeks+...@googlegroups.com**.
> >>>>>>>> For more options, visit this group at http://groups.google.com/**
> >>>>>>>> group/algogeeks?hl=en<
> http://groups.google.com/group/algogeeks?hl=en>
> >>>>>>>> .
> >>>>>>>>
> >>>>>>>
> >>>>>>> --
> >>>>>>> You received this message because you are subscribed to the Google
> >>>>>>> Groups "Algorithm Geeks" group.
> >>>>>>> To post to this group, send email to algo...@googlegroups.com.
> >>>>>>> To unsubscribe from this group, send email to
> >>>>>>> algogeeks+...@googlegroups.com**.
> >>>>>>> For more options, visit this group at http://groups.google.com/**
> >>>>>>> group/algogeeks?hl=en<
> http://groups.google.com/group/algogeeks?hl=en>
> >>>>>>> .
> >>>>>>>
> >>>>>>
> >>>>>> --
> >>>>>> You received this message because you are subscribed to the Google
> >>>>>> Groups "Algorithm Geeks" group.
> >>>>>> To post to this group, send email to algo...@googlegroups.com.
> >>>>>> To unsubscribe from this group, send email to
> >>>>>> algogeeks+...@googlegroups.com**.
> >>>>>> For more options, visit this group at http://groups.google.com/**
> >>>>>> group/algogeeks?hl=en
> >>>>>> <http://groups.google.com/group/algogeeks?hl=en>
> >>>>>> .
> >>>>>>
> >>>>>
> >>>>> --
> >>>>> You received this message because you are subscribed to the Google
> >>>>> Groups "Algorithm Geeks" group.
> >>>>> To post to this group, send email to algo...@googlegroups.com.
> >>>>> To unsubscribe from this group, send email to
> >>>>> algogeeks+...@googlegroups.com**.
> >>>>> For more options, visit this group at http://groups.google.com/**
> >>>>> group/algogeeks?hl=en
> >>>>> <http://groups.google.com/group/algogeeks?hl=en>.
> >>>>>
> >>>>
> >>>> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To view this discussion on the web visit
> >> https://groups.google.com/d/msg/algogeeks/-/SwuLNscTCOoJ.
> >>
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >> http://groups.google.com/group/algogeeks?hl=en.
> >>
> >
> >
> >
> > --
> > Umer
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> > http://groups.google.com/group/algogeeks?hl=en.
> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Umer
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
