### Leetcode #1529: Bulb Switcher IV

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.

#### 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
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!