Question: Suppose you are in a hallway lined with 100 closed lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open or open it if it's closed - call this toggling the lockers. You continue toggling every nth locker on pass number n. After your hundredth pass of the hallway, in which you toggle only locker number 100, how many lockers are open? Follow up, generalize for k lockers after k passes.

From: Programming Interviews Exposed

Subject: Math and Logic Puzzles

Load Another Question

Select a Subject

Select a Subject Algorithm Analysis Arrays and Strings Bit Manipulation C and Cpp Code Quality Combinatorial Search Concurrency Data Structures Databases Design Patterns Dynamic Programming General Graph Theory Hard Java Knowledge Based Linked Lists Math and Logic Puzzles Moderate Object-Oriented Design Recursion Recursion and Dynamic Programming Soft Skills Sorting and Searching Stacks and Queues System Design and Scalability Testing Threads and Locks Trees and Graphs