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(kn), where k is the number of digits of n.

Answer 1

So this question is based on math.

Let me explain how?

We all know every number has some factors that divide that number or (n%k ==0) where k is the factor of n

for example

10 = {1,2,5,10} these 2 the factors of 10

9 = {1,3,9) these 3 are the factors of 9 ->perfect square

so let's solve one with an example and see what answer comes

N = 5

step 0:1 2 3 4 5

0 0 0 0 0 // initially all are closed

step 1:1 2 3 4 5

1 1 1 1 1 so 1 is a factor of every number and everyone is open now and 1 is also a perfect square

step 2:1 2 3 4 5

1 0 1 0 1 2 is factor of 2 and 4

step 3:1 2 3 4 5

1 0 0 0 1 3 is a factor of 3 only so it closes it

step 4:1 2 3 4 5

1 0 0 1 1 // 4 is factor of 4 so it opens it 4->perfect square

step 5:1 2 3 4 5

1 0 0 1 0 // 5 is factor if 5 so it closes it

so, at last, we see there are 2 boxes that are open 1,4

if we look closely 1 and 4 are a perfect square having only three factors 4 = {1,2,4}

so this is our answer any number that is perfect square will remain open at the last

perfect squares are {1,4,9,16,25,36,49..........and so on}

so I will be writing a code for it with time complexity O(log2(N) )

#include <iostream>

using namespace std;
int open_boxex(int n){
int count = 0;
for(int i = 1;i*i<=n;i++){ // this loop will run only log(n) times so time complexity is O(log(n))
if(i*i<=n){ // checking for perfect square
count++; // if perfect square then increment the count
}
}
return count; // return number of boxes that are open
}
int main()
{
cout<<"Enter the number of boxes\n";
int n;
cin>>n;
cout<<"open boxes are :"<<open_boxex(n);
// n = 4 = {1,4,9,16} so answer would be 4;

return 0;
}

if any doubt, comment below