Bulb Switcher

Medium
436.

Bulb Switcher

MediumMathBrainteaserAmazonGoogleMicrosoftMathWorks

Bulb Switcher is a medium coding problem on math and brainteaser, asked in Amazon, Google, Microsoft and MathWorks interviews.

There are n bulbs, all off. You do n rounds:

  • round 1 toggles every bulb;
  • round 2 toggles every 2nd bulb;
  • round i toggles every i-th bulb;
  • round n toggles only the last bulb.

Return how many bulbs are on after n rounds.

Example 1

Input
n = 3
Output
1
Explanation
Only bulb 1 stays on.

Example 2

Input
n = 0
Output
0

Example 3

Input
n = 1
Output
1

Constraints

  • 0 <= n <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var bulbSwitch = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Bulb Switcher — Solution in Python, Java & C++

Bulb Switcher solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and brainteaser.

Bulb Switcher is a medium coding problem on math and brainteaser, asked in Amazon, Google, Microsoft and MathWorks interviews.

Problem statement

There are n bulbs, all off. You do n rounds:

  • round 1 toggles every bulb;
  • round 2 toggles every 2nd bulb;
  • round i toggles every i-th bulb;
  • round n toggles only the last bulb.

Return how many bulbs are on after n rounds.

Example 1

Input: n = 3
Output: 1
Explanation: Only bulb 1 stays on.

Example 2

Input: n = 0
Output: 0

Example 3

Input: n = 1
Output: 1

Constraints

  • 0 <= n <= 1000000000

Hints for Bulb Switcher

  1. Hint 1

    Bulb k is toggled once per divisor of k, so it ends up on exactly when k has an odd number of divisors.

  2. Hint 2

    Divisors normally pair up — except when the two halves of a pair coincide.

  3. Hint 3

    That happens only for perfect squares, so the answer is floor(sqrt(n)).

How to solve Bulb Switcher

Bulb k is toggled once per divisor of k, so it stays on iff k has an odd number of divisors — exactly the perfect squares. Answer: ⌊√n⌋.

Approach

  1. Return the integer square root of n.

Why it works

Divisors pair up as (d, k/d) except when d = k/d, so only squares have an odd divisor count; the squares up to n number ⌊√n⌋.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Use an integer square root; floating-point sqrt can be off by one at large n.

Reference solution

Python

import math

def bulbSwitch(n: int) -> int:
    return math.isqrt(n)

Java

public static int bulbSwitch(int n) {
    long root = (long) Math.sqrt((double) n);
    while ((root + 1) * (root + 1) <= n) root++;
    while (root > 0 && root * root > n) root--;
    return (int) root;
}

C++

int bulbSwitch(int n) {
    long long root = (long long) sqrt((double) n);
    while ((root + 1) * (root + 1) <= n) root++;
    while (root > 0 && root * root > n) root--;
    return (int) root;
}

JavaScript

var bulbSwitch = function(n) {
    let root = Math.floor(Math.sqrt(n));
    while ((root + 1) * (root + 1) <= n) root++;
    while (root * root > n) root--;
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue