We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Bulb Switcher II

Number: 672

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

You are given n bulbs that are all turned on initially. There are four buttons, each of which toggles the bulbs in a different pattern:

  • Button 1: Flip every bulb.
  • Button 2: Flip all even-numbered bulbs.
  • Button 3: Flip all odd-numbered bulbs.
  • Button 4: Flip bulbs numbered as 3k+1 (i.e. 1, 4, 7, ...).

You must perform exactly "presses" button presses, and you can press any button more than once. The goal is to determine the number of different possible statuses of the bulbs after performing all the presses.

Key Insights

  • When presses equals 0, there is only one possible configuration (all bulbs remain on).
  • Due to symmetry and overlap among the operations, the number of unique states is limited regardless of how many bulbs there are.
  • For n greater than 3, only the first three bulbs determine the overall state, so the problem reduces to a small state space.
  • The results depend both on n (i.e. n=1, n=2, or n>=3) and the number of presses.
  • Use mathematical reasoning and case analysis to derive the answer:
    • For n = 1, there can be at most 2 states.
    • For n = 2, the maximum unique states are 3 for 1 press and 4 for more than 1 press.
    • For n >= 3, the answers are: 1 (0 presses), 4 (1 press), 7 (2 presses), and 8 (3 or more presses).

Space and Time Complexity

Time Complexity: O(1) – The solution uses a fixed number of condition checks. Space Complexity: O(1) – Only constant extra space is required.

Solution

We solve the problem through case analysis. First, handle the case when presses equals 0 – simply return 1. Next, split scenarios by the number of bulbs:

  • If n equals 1, regardless of which button is pressed (if presses > 0), only 2 distinct states are possible.
  • If n equals 2, then:
    • If presses equals 1, then 3 distinct states are possible.
    • Otherwise (presses >= 2), 4 states will be achievable.
  • For n greater than or equal to 3:
    • With 1 press, 4 states are possible.
    • With 2 presses, 7 states can be achieved.
    • With 3 or more presses, it is possible to reach all 8 valid states. This reasoning is based on the observation that the operations become interdependent beyond the first few bulbs, which limits the number of distinct outcomes.

Code Solutions

# Python solution with line-by-line comments

def flipLights(n: int, presses: int) -> int:
    # If there are no presses, the bulbs remain in their initial state.
    if presses == 0:
        return 1

    # For n == 1, only 2 distinct statuses possible when any button is pressed.
    if n == 1:
        return 2

    # For n == 2, the possibilities vary with number of presses.
    if n == 2:
        # With 1 press, 3 distinct statuses are possible.
        if presses == 1:
            return 3
        else:
            # For presses >= 2, 4 distinct statuses.
            return 4

    # For n >= 3, the number of distinct states depends on the number of presses.
    if presses == 1:
        return 4  # 4 possible statuses
    elif presses == 2:
        return 7  # 7 possible statuses
    else:
        # For presses >= 3, all 8 possible statuses can be achieved.
        return 8

# Example usage:
print(flipLights(1, 1))  # Output: 2
print(flipLights(2, 1))  # Output: 3
print(flipLights(3, 1))  # Output: 4
← Back to All Questions