[algogeeks] Re: An interesting problem from Code4bill second round

[himanshu]

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