Wednesday, October 24, 2012

Problem 2: Student Counting Problem

Problem 2: How will you count the number of students in a classroom in quickest possible manner.

Solution: Perform the following steps:

  1. Ask the class to stand up and make pairs.
  2. If one student is left out write '1' else write 0.
  3. Tell the left out student to sit down and ask one person in each group to sit down.
  4. Repeat the process and append '1' or '0' to your number, until no student is left standing. 

You will get the binary representation of the number of students in reverse order.
Example: Lets say there are 23 students in the class
Students standing 23 11 5 2 1 0
Solution 1 1 1 0 1 0
we have a string 111010, and the binary representation of 23 is 010111.
Complexity: This is just using divide and conquer O(lg n)

No comments:

Post a Comment