Light bulbs


  • 0

    You have a bunch of light bulbs. Store them as you wish. Implement a function that tells you if the light is on or off given its index and another one that toggles the state of the light bulbs given a start and end index.


  • 0
    R

    First, ask the call ratio of query() to toggle(). If one of them is relatively larger than the other, you might consider optimizing the one with more frequent calls down to O(1).

    If the ratio is about 1:1 (same number of calls to both functions), then you are looking for a BIT solution. Check out sample problem #2 of this TopCoder article.


Log in to reply
 

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