Question

Consider a set of n boxes with their positions numbered from 1 to n. Initially all the boxes
are CLOSED. These n boxes are subject to modifications over n iterations as follows. At the ith
iterations the boxes at the positions whose ids are multiples of i are flipped, i.e. changed from
CLOSED to OPEN or vice-versa. For example, at iteration 1, boxes at all positions are
flipped, at iteration 2, boxes at positions 2,4,6,etc. are flipped, at iteration 3, boxes at positions 3,6,9, etc.
are flipped.
Propose an algorithm for find out, that after n such iterations how many boxes will be OPEN.
Note that the answer requires only how many boxes, not their positions. Describe the rationale
for the algorithm, give the pseudocode, and its complexity. Grading scheme: (your grade will be
based on whichever class your algorithm falls in)
- For algorithms with complexity O(n2) or higher.
- For algorithms with complexity O(kn), where k is the number of digits of n.
- For algorithms with complexity O(M(k)), where k is the number of digits of n, and M(k) is
the complexity of multiplying two k digit numbers.

Answer 1

Lets consider an example where n=24 boxes. So, we will visit the box for its every divisor i.e. 1 and 24, 2 and 12, 3 and 8, 4 and 6. Initially it is closed. So at 1, box will be flipped i.e opened and closed at divisor '2'. It will be again opened at '3' and closed at '4', opened at '6' and closed at '8' and opened at '12' and closed at '24'. So for every pair of divisors the box will end up just as in its initial state.

But this is not always the case. Consider n=16 boxes. for n= 16, the divisors are 1 and 16, 2 and 8, 4 and 4. But we see that '4' is repeated i.e. we have odd number of divisors here because 16 is a perfect square. So the box number 16  will open for 1 and closed for 2, opened for '4' and closed for '8' and again opened for '16'. So, the boxes which are perfect squares will remain opened.

Hence, for a set of 'n' boxes, we will need to find the number of perfect squares from 1 to 'n' which will give the number of boxes opened.

Algorithm :-

Step 1:- Initialize a variable 'i' to '1' . Take a count variable 'count' and initialize it with '0'.

Step 2:- calculate i*i and store it in a variable 'x' i.e. x=i*i.

If x<=n, increase count and i by 1 i.e, count++ and i++. and repeat step 2.

else go to step 3.

Step 3:- 'count' variable will give the number of perfect squares from 1 to n

PseudoCode for it:-

int i=1;

int count =0;

while (i*i<=n)

x=i*i;

if(x<=n) {

count ++; i++; }

else

break;

print("No of boxes opened i.e. number of perfect squares = ",count)

Time complexity :-

This algorithm falls under the third category i.e  o(M(k)), as we have k digits number for every 'i' in while loop and we are multiplying the k-digit number by itself i.e. two times. And we know that M(k) is the complexity of multiplying two k-digit number.

If you like the answer, please support by upvoting it. And if you have any doubts regarding this, please comment in the comment section, I am sure to help.