Java Solution in 1ms Not using Sqrt()


  • -1
    T

    Basic scenario is the comparison between count of the "on" bulb and total amount of bulb are as following

    total & count

    0 & 0

    1-3 & 1

    4-8 & 2

    9-15 & 3

    17- 24 & 4....

    so regardless of the beginning 0-3 since 0 is 0, 1-3 with a count of 1

    ** the difference between "total" 3---8---15----24 is 5,7,9....

    so just compare the sum(3+5+7+9+...) and n, we will get the count of bulb's on.

    Any mistake please let me know

    public int bulbSwitch(int n) {

        if (n == 0) return 0;
        int count = 1;
        for (int sum = 3, end = 5, digit = 2; sum < n; end += 2, count++, digit++) {
            sum = (3 + end) * digit / 2;
        }
        return n <= 3 ? 1 : count;
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.