We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Bulb Switcher

Number: 319

Difficulty: Medium

Paid? No

Companies: LinkedIn, Accenture, Meta, Oracle, Amazon, Microsoft, Google

Problem Description

There are n bulbs initially off. In the first round, every bulb is turned on. In subsequent rounds, for the iᵗʰ round, every iᵗʰ bulb is toggled (switched on if off or off if on). After n rounds, return the number of bulbs that remain on.

Key Insights

  • A bulb is toggled once for each of its divisors.
  • Only bulbs at positions with an odd number of divisors remain on.
  • Only perfect squares have an odd number of divisors.
  • The answer is the number of perfect squares ≤ n.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The problem can be solved by recognizing that a bulb ends up on only if it has been toggled an odd number of times, which happens when the bulb's position is a perfect square. For each number i from 1 to n, if i is a perfect square (i = j² for some integer j), it will be toggled an odd number of times. Therefore, the problem reduces to counting how many perfect squares exist between 1 and n, which is the same as computing the floor of the square root of n.

Code Solutions

import math

def bulbSwitch(n):
    # Calculate the integer part of the square root of n
    # which gives the count of perfect squares <= n.
    return int(math.sqrt(n))

# Example usage:
print(bulbSwitch(3))  # Output: 1
← Back to All Questions