Bulb Switcher Solution for Accenture
Company: Accenture · Difficulty: Medium · Topics: Math, Brain Teaser
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 ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Find how many bulbs are on after n rounds.
Key Understanding:
- Initially all bulbs are off
- Round 1: Turn on all bulbs (1, 2, 3, ..., n)
- Round 2: Turn off every 2nd bulb (2, 4, 6, ...)
- Round 3: Toggle every 3rd bulb (3, 6, 9, ...)
- Round i: Toggle every ith bulb
- Final state: Count bulbs that are on
Examples
Example 1:
Input: n = 3
Output: 1
Explanation:
- Initial state: [off, off, off]
- Round 1: [on, on, on]
- Round 2: [on, off, on]
- Round 3: [on, off, off]
- Final state: Only bulb 1 is on
Example 2:
Input: n = 1
Output: 1
Explanation:
- Initial state: [off]
- Round 1: [on]
- Final state: Bulb 1 is on
Example 3:
Input: n = 0
Output: 0
Explanation:
- No bulbs, so 0 bulbs are on
Intuition
The key insight is to understand which bulbs will be toggled an odd number of times.
Mathematical Insight:
- A bulb will be toggled once for each of its factors
- Bulb i will be toggled in rounds 1, 2, 3, ..., i if i is divisible by those numbers
- A bulb ends up on if it's toggled an odd number of times
- Perfect squares have an odd number of factors (including the square root)
- Non-perfect squares have an even number of factors
Why Perfect Squares Work:
- For a perfect square k², the factors are: 1, 2, 3, ..., k, ..., k²
- The factor k appears only once (when k = √k²)
- All other factors come in pairs (a, k²/a)
- Total factors = odd number → bulb ends up on
Approach
Approach 1: Mathematical (Optimal)
Algorithm:
1. Count the number of perfect squares ≤ n
2. Return the count
Why This Works:
- Only perfect squares have an odd number of factors
- Only bulbs at perfect square positions end up on
- Count = floor(√n)
Approach 2: Simulation
Algorithm:
1. Create an array of n bulbs (all off)
2. For each round i from 1 to n:
- Toggle every ith bulb
3. Count bulbs that are on
Approach 3: Factor Counting
Algorithm:
1. For each bulb i from 1 to n:
- Count its factors
- If odd number of factors, bulb ends up on
2. Return count of bulbs with odd factors
Dry Run
Let's trace through Example 1: n = 3
Mathematical Approach:
- Perfect squares ≤ 3: 1 (1² = 1)
- Count = 1
- Result: 1
Simulation Approach:
- Initial: [off, off, off]
- Round 1: [on, on, on]
- Round 2: [on, off, on]
- Round 3: [on, off, off]
- Count on bulbs: 1
Factor Counting:
- Bulb 1: factors = [1] → odd → on
- Bulb 2: factors = [1, 2] → even → off
- Bulb 3: factors = [1, 3] → even → off
- Result: 1
Key Insights
1. Perfect Squares: Only perfect squares have odd number of factors
2. Mathematical Solution: Count perfect squares ≤ n
3. Efficiency: O(1) time complexity with mathematical approach
4. Pattern Recognition: The result is floor(√n)
Edge Cases
1. n = 0: Return 0
2. n = 1: Return 1
3. Large n: Mathematical approach handles efficiently
4. Perfect Square n: Include n in count
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Mathematical (Optimal)
Time Complexity: O(1) - Constant time
Space Complexity: O(1) - Constant space
Solution 2: Simulation
Time Complexity: O(n²) - For each round, toggle bulbs
Space Complexity: O(n) - Array to store bulb states
Solution 3: Factor Counting
Time Complexity: O(n * √n) - For each bulb, find factors
Space Complexity: O(1) - Constant space