ther are N numbers frm 1 to N and starting from index 1 we will keep deleting every alternate going in cyclic order with array. Only one element will be left at the end.
Tell us the index of element in array we started.
e.g.
there are 5 nums
1 2 3 4 5
then after 1st iteration 1 3 5 will be remained.
.. then 1 will be next to be elliminated and then 5
3 will remain alone...
give sum efficient algorithm to calculate which numer will remain at the end
Answer: 2*(n-2^p)+1
where p=floor(log2 n)
Tell us the index of element in array we started.
e.g.
there are 5 nums
1 2 3 4 5
then after 1st iteration 1 3 5 will be remained.
.. then 1 will be next to be elliminated and then 5
3 will remain alone...
give sum efficient algorithm to calculate which numer will remain at the end
Answer: 2*(n-2^p)+1
where p=floor(log2 n)
Comments
Post a Comment