2 short lines, simple formula

  • 2
    int flipLights(int n, int m) {
        n = min(n, 3);
        return min(1<<n, 1+m*n);

    I can't (yet?) explain the 1+m*n part, though. Really I just wrote a brute force solution, looked at the results for all cases where n, m ≤ 10 and found a formula for the pattern I saw :-)

  • 3

    Brilliant! Here are some analyses inspired by your idea.
    Also see my two line solution here
    Operations: O(flip odds), E(flip evens), A(flip all), T(flip 3k + 1), N(flip nothing)
    O + O = N, E + E = N, A + A = N, T + T = N
    O + E = A, O + A = E, E + A = O
    Exclusive statuses :
    n > 2:
    ① N
    ② O
    ③ E
    ④ A
    ⑤ T
    ⑥ O + T
    ⑦ E + T
    ⑧ A + T

    n = 2 (remove all T related statuses):
    ① N
    ② O
    ③ E
    ④ A

    n = 1(remove all T, E, A related statuses):
    ① N
    ② O

    Steps needed to all status( always can plus 2 * k)
    ① can only be achieved by 0, 2 steps
    ②,③,④ can be achieved by either 1 or 2 steps
    ⑤ can only be achieved by 1 steps
    ⑥,⑦,⑧ can only be achieved by 2 steps,

    0 steps -> ①
    1 steps -> ②,③,④,⑤
    2 steps -> ①,②,③,④,⑥,⑦,⑧
    more than 2 steps -> ①, ②, ③, ④, ⑤, ⑥, ⑦, ⑧

    0_1504740290430_Screen Shot 2017-09-06 at 4.23.25 PM.png

  • 0

    @Ipeq1 Hmm, sorry, the meaningless names A to D, with effects in an order different from the problem statement (and thus conflicting with what I already have in my head), made it unnecessarily hard to read and I stopped early on. I think it might work better with meaningful names like "all", "even", "odd", "thirds", "none" or even A, E, O, T, N if you insist on single letter names.

  • 0

    @StefanPochmann Just edited all those A,B,C,D,Es. Sorry, but I'm not really good at composing some article.
    But I think the conclusion drawn on the picture was actually what really matters and helps to conduct to some straightforward answers.

  • 0

    @Ipeq1 Ok I've read it now. It does give more insights, especially seeing the (5) drop out and the others staying because you can "waste" a move with them. One of these insights is that I'm now more convinced that my 1+m*n really doesn't make sense :-). Looks more and more like I really just found a nice formula for something that itself is really not nice.

    I was somewhat hoping it would be like for the problem of xor-ing the integers from 0 to n. If you do that, i.e., print out the results and observe the pattern, you'll see an easy pattern as well. But there the pattern is very much meaningful.

    Of course one key difference is that in the xor-problem the n can go arbitrarily high. In this problem here, my 1+m*n is so quickly dominated by 1<<3. Not much of a pattern if it's just a handful of values. Oh well, I still like it for being so short.

Log in to reply

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