C++, concise code, O(1)


  • 17
    Z

    When n <= 1, the solution is trial.

    From the 4 types of operations,

    1. Flip all the lights.
    2. Flip lights with even numbers.
    3. Flip lights with odd numbers.
    4. Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...
    

    There are three important observations:

    1. For any operation, only odd or even matters, i.e. 0 or 1. Two same operations equal no operation.
    2. The first 3 operations can be reduced to 1 or 0 operation. For example, flip all + flip even = flip odd. So the result of the first 3 operations is the same as either 1 operation or original.
    3. The solution for n > 3 is the same as n = 3.
      For example, 1 0 0 ....., I use 0 and 1 to represent off and on.
      The state of 2nd digit indicates even flip; The state of 3rd digit indicates odd flip; And the state difference of 1st and 3rd digits indicates 3k+1 flip.

    In summary, the question can be simplified as m <= 3, n <= 3. I am sure you can figure out the rest easily.

    class Solution {
    public:
        int flipLights(int n, int m) {
            if (m == 0 || n == 0) return 1;
            if (n == 1) return 2;
            if (n == 2) return m == 1? 3:4;
            if (m == 1) return 4;
            return m == 2? 7:8;
        }
    };
    

  • 2
    A

    Great to see such concise code, but please explain the logic behind it. Thanks.


  • 0
    This post is deleted!

  • 0
    M

    After reading your solution, I write my own Cpp code in a more detailed way.

    class Solution {
    public:
        int flipLights(int n, int m) {
            if (n == 0 || m == 0) return 1;
        
            if (m == 1 && n == 1) return 2;
            if (m == 1 && n == 2) return 3;
            if (m == 1 && n == 3) return 4;
            if (m == 2 && n == 1) return 2;
            if (m == 2 && n == 2) return 4;
            if (m == 2 && n == 3) return 7;
            if (m == 3 && n == 1) return 2;
            if (m == 3 && n == 2) return 4;
            if (m == 3 && n == 3) return 8;
        
            if (m >= 3 && n >= 3) return 8;
            if (m >= 3) return flipLights(n, 3);
            if (n >= 3) return flipLights(3, m);
        }
    };

  • 1
    S

    not sure through this question - what coding skill would interviewer want to assess


  • 1
    B

    @mgh said in C++, concise code, O(1):

    After reading your solution, I write my own Cpp code in a more detailed way.

    class Solution {
    public:
        int flipLights(int n, int m) {
            if (n == 0 || m == 0) return 1;
        
            if (m == 1 && n == 1) return 2;
            if (m == 1 && n == 2) return 3;
            if (m == 1 && n == 3) return 4;
            if (m == 2 && n == 1) return 2;
            if (m == 2 && n == 2) return 4;
            if (m == 2 && n == 3) return 7;
            if (m == 3 && n == 1) return 2;
            if (m == 3 && n == 2) return 4;
            if (m == 3 && n == 3) return 8;
        
            if (m >= 3 && n >= 3) return 8;
            if (m >= 3) return flipLights(n, 3);
            if (n >= 3) return flipLights(3, m);
        }
    };
    

    if n==1, no matter how many m you have, it can only have 2 results, on or off.


  • 0
    B

    @messi14 said in C++, concise code, O(1):

    Maybe this could help:
    https://www.khanacademy.org/math/math-for-fun-and-glory/puzzles/brain-teasers/v/light-bulb-switching-brain-teaser

    That's a slightly different question, which is covered by Leetcode319 and can be answered with a one liner.


Log in to reply
 

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