PROBLEM STATEMENT
The Locker Problem is a very famous problem. There are a line of lockers, all
initially closed. Person A walks by and opens every locker. Person B then
walks by and closes every other locker. Person C then walks by and "changes
the status" of every third locker - that is, if it is open he closes it, and if
its closed he opens it. Person D then changes the status of every fourth
locker. This process repeats forever. Which lockers are open? The answer is
lockers 1, 4, 9, 16,... will be open because they are perfect squares and have
an odd number of factors.
Example: O represents an open locker, C represents a closed locker.
10 20 30 40
123456789 123456789 123456789 123456789 12...
Initially: CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
After person A: OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
After person B: OCOCOCOCOCOCOCOCOCOCOCOCOCOCOCOCOCOCOCOCOC...
After person C: OCCCOOOCCCOOOCCCOOOCCCOOOCCCOOOCCCOOOCCCOO...
After person D: OCCOOOOOCCOCOCCOOOOOCCOCOCCOOOOOCCOCOCCOOO...
You are to implement a variant of the locker problem. There are initially 1000
closed lockers. You are given an int[] of n people. If the ith element of the
int[] is d, then the ith person changes the status of every d lockers. For
example, if the 3rd element of the int[] is 5, then the third person changes
the status of every 5th locker, i.e. closes the ones that are open and opens
the ones that are closed. Return the number of open lockers after every person
has altered the lockers. See examples below.
DEFINITION
Class: Lockers
Method: numOpen
Parameters: int[]
Returns: int
Method signature (be sure your method is public): int numOpen(int[] people);
TopCoder will ensure that:
- people will have between 0 and 20 elements, inclusive.
- each element of people is between 1 and 1000 inclusive.
EXAMPLES
1. If people = {2}.
- The first person opens every second locker. Return 500.
2. If people = {2, 5}.
- The first person opens every second locker. 500 lockers open.
- The second person changes the status of every 5th locker. 200 lockers are
changed - 100 opened, and 100 closed. So 500 lockers remain open. Return 500.
3. If people = {1, 2, 3, 4, 5}. Return 547.
4. If people = {2, 2, 4, 6}. Return 250.