nice solution, Dave!
@Umer -- if the sought ele is first, then Dave's code has it sitting in the
variable temp for a little while. Loop will stop when size is 0, since
arr[0]==elem. Now he throws temp back into arr[0], which will return index
0 from the last compare line.
On Wednesday, October 3, 2012 2:08:56 AM UTC-4, Umer Farooq wrote:
>
> @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.8...@gmail.com<javascript:>
> > 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....@gmail.com <javascript:>> 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 <rafiw...@gmail.com <javascript:>>
>> 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 algo...@googlegroups.com<javascript:>
>> .
>> >> To unsubscribe from this group, send email to
>> >> algogeeks+...@googlegroups.com <javascript:>.
>> >> 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 algo...@googlegroups.com<javascript:>
>> .
>> > To unsubscribe from this group, send email to
>> > algogeeks+...@googlegroups.com <javascript:>.
>> > 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 algo...@googlegroups.com<javascript:>
>> .
>> To unsubscribe from this group, send email to
>> algogeeks+...@googlegroups.com <javascript:>.
>> 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/MCOQyzdtcAMJ.
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.
