How Does A Programmer Think!!

Hi, guys I know you all miss me a lot! me to buddies!

You are all shocked, right? while looking at the Nannaku Prematho poster!

Don't worry, coming to the point!!

Last Night I was watching the movie Nannaku Prematho Movie, at 56:23 minutes I was amazed by the question asked by Jagapathi Babu(Villain) and the Question was,

100 people standing in a circle in an order of 1 to 100. No.1 has a sword and he kills the next person(No.2) and gives the sword to the next (No.3) and No.3 kills the next person(No.4) and gives the sword to the next(No.5). All people do the same until only one survives. Who will survive at the last!!?

By listening to that question we the programmers think that it was like a circular linked list problem. And we can solve it like this!

void _NannakuPrematho_(struct Node *head)
{ 
	struct Node *temp=head; 
	do 
	{ 
		if(temp->next!=NULL)
		{ 
			temp->next=temp->next->next; 
	      	        temp=temp->next; 
	     		head=temp; 
     		} 
     	}
     	
}         

When we are in DAA(Design And Analysis Of Algorithms), as Algorithmist we can solve any problem by analyzing it and writing a desired algorithm based on time and space complexities!!

Like that we wrote!

//Recurrence Relation

T(n) = 2T(n/2)-1 // if 'n' is even.

T(n) = 2T(n/2) +1 // if 'n' is odd.

T(1) = 1 // base case 
 
For n = 100   // 100 people right?
 
T(100)=2T(50)−1

      =2(2T(25)−1)−1  =  4T(25)−3 

      =4(2T(12)+1)−3  =  8T(12)+1 

      =8(2T(6)−1)+1   =  16T(6)-7 

      =16(2T(3)-1)−7  =  32T(3)-23 

      =32(2T(1)+1)−23 =  64T(1)+9
 
      =64∗1+9
 
      =73          

Hence, we solved it! the 73rd person will survive in the last!! :)

programming is fun. Cheers!

Anyway, the movie is good!

If you like this post just share it with your friends!! and like it.

Do connect/follow for more(99999999999999...)