CODEWITHSUNDEEP
pythonmath
user6461129
user6461129

Reputation:

Incremental Door Pass Riddle - Only Square Positions Open

There are hundred doors, all closed to start with, a robot makes 100 passes, such that on every pass it increments by the next starting token. Thus,

1, 2, 3,.....
2, 4, 6, 8,....
3, 6, 9, 11,....
4, 8, 12, 16,....
.......
100

Every time it visits a door it switches from its current state, thus closes if it was open and opens if it was closed. After 100 passes find the number of doors that are open.

The problem is trivial, here's my solution,

def door_traversal():
    arr = []
    arr = [0 for i in range(101)]
    for i in range(1, 101, 1):
        for j in range(i, 101, i):
            arr[j] = not arr[j]

    count = 0
    for i in range(1, 101, 1):
        if arr[i] == 1:
            count += 1
    return count

The answer is 10 and on checking how do I get this number 10, it seems all the door indices which are perfect square are open.Thus the open doors are

1,4,9.....

What I've been trying to understand is the math behind, this. Any help with that?

Upvotes: 0

Views: 82

Answers (1)

Kevin L
Kevin L

Reputation: 1066

Factorize the numbers - each factor indicates the 'pass' through which the door is open/closed. Square numbers have odd numbers of factors (9 = 1,3 [twice],9). Everything else has an even number of factors

Upvotes: 3

Related Questions