Got this code on codechef:
The captain of the ship TITANIC is a little .... off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game.
The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position.
Initially, standing people have numbers - 1,2,3,4,5...
After first pass, people left are - 2,4,...
After second pass - 4,....
And so on.
You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected.
Starting off, the first option was brute forcing.
Then came to my mind a better solution. I found out that the position can always be determined by using the inequality:
2k <= n
for largest value of k.
This reduced the running time to O(log n).
While writing a code for this, I realized that this can be done in constant time by using floor(log 2 n).
This gives largest value of 'k'. Now using power function of Math Library, find the position.
The captain of the ship TITANIC is a little .... off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game.
The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position.
Initially, standing people have numbers - 1,2,3,4,5...
After first pass, people left are - 2,4,...
After second pass - 4,....
And so on.
You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected.
Starting off, the first option was brute forcing.
Then came to my mind a better solution. I found out that the position can always be determined by using the inequality:
2k <= n
for largest value of k.
This reduced the running time to O(log n).
While writing a code for this, I realized that this can be done in constant time by using floor(log 2 n).
This gives largest value of 'k'. Now using power function of Math Library, find the position.
No comments:
Post a Comment