PROBLEM LINK:
Author: mesksr
Editorialist: mesksr
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Math
PROBLEM:
There are N bulb, numbered from 1 to N. All are initially off.
People numbered from 1 to N go and toggle the state of the bulbs, which are there multiple.
EXPLANATION:
Each bulb is toggled by all its divisors.
We know that all perfect square number have odd number of divisors and rest of the numbers have even number of divisors.
If the bulb is initially off, after even number of toggles, it will become off. Similarly, after odd number of toggles, it will become on.
So, if N is the input, we just have to calculate the number of perfect squares less than or equal to N.
Note : We need to take long long int to pass all the test cases.
AUTHOR’S SOLUTION:
Author’s solution can be found here.