hi himansu ,
i think ur algo works in n^2 time.
regards,
neeraj goel
On 2/3/06, himanshu <[EMAIL PROTECTED]> wrote:
hi every1 ,
I m Himanshu Sawhney , MCA student from D.U. Just joined this group .
I've formed a sol. plz chk it out
mark_last_cell(start,end,number)
{
if(start==end)
a[start]=1
return
mid=(start+end)/2
mark_last(start,mid-1,number-1)
a[mid]=1;
unmark(start,mid-1,number-1)
marl_last_cell(mid+1,end,number-1)
}
unmark(start,end,number)
{
if(start==end)
a[start]=0
return
mid=(start+end)/2
unmark(mid+1,end,number-1)
mark_last_cell(start,mid-1,number-1)
a[mid]=0
unmark(start,mid-1,number-12)
}
algo for mark_last_cell is like this
divide the array into three part
1)from start to mid -1
2)mid element
3)from mid+1 to end
fill last element of first array using number-1 1's
then mark middle element 1
we have know use all 1's
now unmark 1st array
and then fill last array using number-1 1's as middle element is 1
and algo for unmark is also in simmiliar term
but this algo takes exponential time
for array os size 63 it takes 364 toggles
regards,
Himanshu Sawhney
