algoadvance

Leetcode 319. Bulb Switcher

Problem Statement

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off, or turning off if it’s on). For the i-th round, you toggle every i-th bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Clarifying Questions

  1. Input/Output Constraints:
    • What is the range of n? For typical LeetCode problems, assume 1 <= n <= 10^9.
  2. Understanding the toggling behavior:
    • Each bulb i is toggled in each round k where k is a divisor of i.
  3. Final Output:
    • Return the number of bulbs that remain on after all rounds of toggling.

Strategy

  1. Key Insight:
    • A bulb i ends up being toggled in each round corresponding to its divisors. Hence a bulb that is toggled an odd number of times will be on at the end.
    • Only perfect squares have an odd number of divisors. For example, 36 has divisors 1, 2, 3, 4, 6, 9, 12, 18, 36, and their pairs: 1x36, 2x18, 3x12, 4x9, 6x6. Among these, 6 appears only once.
  2. Conclusion:
    • The number of bulbs that remain on corresponds to the number of perfect squares less than or equal to n.
    • The number of perfect squares up to n is floor(sqrt(n)).

Code

#include <cmath>

class Solution {
public:
    int bulbSwitch(int n) {
        return floor(sqrt(n));
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI