algoadvance

Leetcode 672. Bulb Switcher II

Problem Statement

You have n bulbs in a row numbered from 1 to n. Initially, all the bulbs are turned on. You are given a number m, which represents the number of operations. You can perform one of the following operations exactly once on any bulb:

  1. Flip all the bulbs.
  2. Flip every second bulb.
  3. Flip every third bulb.
  4. Flip bulbs with positions that are 1 modulo 3 (1, 4, 7, …).

Given n and m, return the number of different possible states of the n bulbs after performing all m operations.

Clarifying Questions

  1. What do the operations mean by “flip”?
    • “Flip” means changing the state of the bulb: if the bulb is on, it turns off; if it is off, it turns on.
  2. How does the initial state affect the result?
    • Initially, all bulbs are turned on.
  3. What constraints are on n and m?
    • Typically, 1 <= n <= 1000 and 0 <= m <= 1000, but for practical problem-solving, there are much smaller constraints due to combinatorial limits.
  4. What is the smallest and largest possible value for the primary elements (n and m)?
    • The smallest value is 1 and the largest is generally 1000 for n and m.

Strategy

  1. Explore Patterns:
    • Due to periodic flipping, patterns will emerge which simplify the problem.
    • For large values of n (more than 6), the pattern starts to repeat, so we don’t need to worry about n greater than 6.
    • When n is greater than 6, we can reduce n to 6 because all bulbs after the 6th bulb will encounter similar shifts and flips as the first 6 bulbs.
  2. Cases Based on m:
    • When looking at the number of different states possible, we realize that beyond 4 operations, the state space saturates and different operations might not create new distinct states.
    • Thus, we focus mainly on the 4 operations leading to these primary cases:
      • m == 0: Only 1 state (initial).
      • m == 1: Up to 4 distinct states.
      • m == 2: Up to 7 distinct states.
      • m >= 3: All possible states (8 distinct states with n reduced to 6).

Code

Let’s implement the above logic with C++:

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int flipLights(int n, int m) {
    // Simplify the problem by reducing n to max 6
    if (n > 6) n = 6;
    
    unordered_set<vector<int>> states;
    
    // Explanation based on `n` and `m`:
    if (m == 0) return 1; // No operations => 1 state
    
    if (m == 1) {
        if (n == 1) return 2; // All on or all off 
        if (n == 2) return 3; // 11, 00, 10 (or 01)
        return 4; // max for up to 6 bulbs
    }
    
    if (m == 2) {
        if (n == 1) return 2; // All on or all off 
        if (n == 2) return 4; // more combinations 11, 00, 10, 01
        return 7;
    }
    
    if (m >= 3) {
        if (n == 1) return 2;  // All on or all off 
        if (n == 2) return 4;  // max for 2 bulbs
        return 8;
    }
    
    return 8; // Simplification for any case not directly matched.
}

int main() {
    // Example test cases
    cout << flipLights(1, 1) << endl;     // Output: 2
    cout << flipLights(2, 1) << endl;     // Output: 3
    cout << flipLights(3, 1) << endl;     // Output: 4
    cout << flipLights(1, 0) << endl;     // Output: 1
    cout << flipLights(1, 2) << endl;     // Output: 2
    cout << flipLights(2, 2) << endl;     // Output: 4
    cout << flipLights(3, 2) << endl;     // Output: 7
    return 0;
}

Time Complexity

This solution efficiently handles the constraints and gives the correct number of possible states for the bulbs after m operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI