Leetcode #1529: Bulb Switcher IV

Link to the Problem

Bulb Switcher IV

Thought Process

Certainly, a “Flip” is a must when the current status of a bulb at index i and it’s the target status are not the same.

Initially all bulbs are OFF i.e. 0 and when a bulb at index i is flipped, every bulb after (in the right -> direction) that bulb gets flipped. So it only makes sense to start getting the status of the bulbs correct int the left to right order.

Whenever the flip is necessary, we make the flip which changes the status of the remaining bulbs. We will maintain the status of bulbs in a variable. As all the remaining bulbs are going to have the same status, just a variable is enough instead of an entire array. This is what makes the algorithm efficient. We will keep track of the status of the bulbs as we make flips.

Initially all bulbs are 0, so say status = 0.
Bulb 0 is 0 initially.

  1. If we want it to be 0, we don’t have to make a flip.
  2. If we want it to be 1, we must make a flip. This will change the status of remaining bulbs and they will be ON i.e. 1, so we will also make status as 1.
    Whenever we see the status to be different from what the target is, we must make a flip and this will also change the status of remaining bulbs.
Leetcode #1529: Bulb Switcher IV - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms
Leetcode #1529: Bulb Switcher IV

Algorithm

  1. Initial status of all bulbs is OFF i.e. 0.
  2. For each bulb
    1. If the status is not same as target
      1. Make a flip & this toggles the status.
  3. Return the number of flips made along the way.

Code

class Solution {
inline char toggle(char c) {
return c == '0' ? '1' : '0';
}
public:
int minFlips(string target) {
int n = target.size(); // Total bulbs.
int flips = 0; // Final answer.
char status = '0'; // This stores the status of bulbs that
// are ahead of current index `i`.
for (int i=0; i<n; i++) { // For each bulb -
if (status != target[i]) { // If what we want is different from what
// it is at this moment, make a flip.
flips++; // We made a flip.
status = toggle(status); // Now status of remaining
// bulbs have changed.
}
}
return flips; // Awesome, return the answer now.
}
};
view raw Leetcode_1529.cpp hosted with ❤ by GitHub

Just so you know, this problem can also be considered as a dynamic programming problem. Although I will leave the implementation as an exercise, here is how the function in mathematical way would look like.

F(i) = (target[i] == '1') ____________________ i = 0
     = F(i-1) + (target[i-1] == target[i]) ___ Otherwise

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

Similar Problems

Leetcode #319: Bulb Switcher
Leetcode #672: Bulb Switcher II
Leetcode #1375: Bulb Switcher III



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s