DMITRII’s Substack

Share this post

Leetcode daily # 27.04.2023

dmitriisamoilenko.substack.com

Leetcode daily # 27.04.2023

[319. Bulb Switcher]

DMITRII SAMOILENKO
Apr 27, 2023
Share
Share this post

Leetcode daily # 27.04.2023

dmitriisamoilenko.substack.com

27.04.2023

319. Bulb Switcher medium

fun bulbSwitch(n: Int): Int {
    if (n <= 1) return n
    var count = 1
    var interval = 3
    var x = 1
    while (x + interval <= n) {
        x = x + interval
        interval += 2
        count++
    }
    return count
}

blog post

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/193

Intuition

Let’s draw a diagram and see if any pattern here:

//      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
//
// 1    1 1 1 1 1 1 1 1 1  1 1  1  1  1  1  1  1  1  1
// 2      0 . 0 . 0 . 0 .  0 .  0  .  0  .  0  .  0  .
// 3        0 . . 1 . . 0  . .  1  .  .  0  .  .  1  .
// 4          1 . . . 1 .  . .  0  .  .  .  1  .  .  .
// 5            0 . . . .  1 .  .  .  .  1  .  .  .  .
// 6              0 . . .  . .  1  .  .  .  .  .  0  .
// 7                0 . .  . .  .  .  1  .  .  .  .  .
// 8                  0 .  . .  .  .  .  .  0  .  .  .
// 9                    1  . .  .  .  .  .  .  .  1  .
// 10                      0 .  .  .  .  .  .  .  .  .
// 11                        0  .  .  .  .  .  .  .  .
// 12                           0  .  .  .  .  .  .  .
// 13                              0  .  .  .  .  .  .
// 14                                 0  .  .  .  .  .
// 15                                    0  .  .  .  .
// 16                                       1  .  .  .
// 17                                          0  .  .
// 18                                             0  .
// 19                                                0

One rule is: the number of switches for each new value is a number of divisors.
Another rule: we can reuse the previous result.
However, those rules didn’t help much, let’s observe another pattern: diagonal sequence have increasing intervals of zeros by 2

Approach

Use found law and write the code.

Complexity

  • Time complexity:
    That is tricky, let’s derive it:

    \(n = 1 + 2 + (1+2+2) + (1+2+2+2) + (…) + (1+2k)\)

    or

    \(n = \sum_{i=0}^{k}1+2i = k(1 + 2 + 1 + 2k)/2\)


    then count of elements in arithmetic progression k is:

    \(O(k) = O(\sqrt{n})\)


    which is our time complexity.

  • Space complexity:
    O(1)

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share
Share this post

Leetcode daily # 27.04.2023

dmitriisamoilenko.substack.com
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing