Cuente los giros mínimos a la derecha para establecer todos los valores en una array

N bombillas están conectadas por un cable. Cada bombilla tiene un interruptor asociado, sin embargo, debido a un cableado defectuoso, un interruptor también cambia el estado de todas las bombillas a la derecha de la bombilla actual. Dado un estado inicial de todas las bombillas, encuentre la cantidad mínima de interruptores que debe presionar para encender todas las bombillas. Puede presionar el mismo interruptor varias veces . 
Nota: 0 representa que la bombilla está apagada y 1 representa que la bombilla está encendida . 
Ejemplos:   

Entrada: A[] = [0 1 0 1]
Salida: 4
Explicación: Presione el interruptor 0 : [1 0 1 0]

    presione el interruptor 1: [1 1 0 1]

    presione el interruptor 2: [1 1 1 0]

    presione el interruptor 3: [1 1 1 1]

Entrada: A[] = [1 0 0 0 0] 
Salida: 1

Enfoque ingenuo:

Mantenga una variable de conteo e itere de 0 a N-1 y verifique cada i si A[i] es 0 incremente el conteo en 1 y cambie todos los valores de i a N-1 como 0 a 1 o 1 a 0  

A continuación se muestra la implementación de la idea anterior:

// C++ code for the Idea
// turn all bulbs on.
 
#include <bits/stdc++.h>
using namespace std;
 
int bulbs(int A[], int N)
{
 
    // To keep track of switch presses so far
    int count = 0;
 
    for (int i = 0; i < N; i++) {
        if (A[i] == 0) {
            A[i] = 1;
            for (int j = i + 1; j < N; j++) {
                if (A[j] == 1)
                    A[j] = 0;
                else
                    A[j] = 1;
            }
            count++;
        }
    }
    return count;
}
 
// Driver code
int main()
{
 
    int states[] = { 0, 1, 0, 1 };
    int N = sizeof(states) / sizeof(states[0]);
 
    // Function Code
    cout << "The minimum number of switches needed are "
         << bulbs(states, N);
}

The minimum number of switches needed are 4

Complejidad Temporal: O(N ² ).
Espacio Auxiliar: O(1).

Enfoque eficiente:

Atraviese la array dada de izquierda a derecha y mantenga presionado el interruptor para apagar las bombillas . Lleve un registro del número de pulsaciones del interruptor hasta el momento. Si el número de pulsaciones es par , eso significa que el interruptor actual está en su estado original, de lo contrario, está en el otro estado. Dependiendo del estado en el que se encuentre la bombilla, podemos incrementar el conteo del número de pulsaciones. 

A continuación se muestra la implementación de la idea anterior:

// CPP program to find number switch presses to
// turn all bulbs on.
 
#include<bits/stdc++.h>
using namespace std;
 
int bulbs(int a[],int n)
{
    // To keep track of switch presses so far
    int count = 0;
 
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        /* if the bulb's original state is on and count
        is even, it is currently on...*/
        /* no need to press this switch */
        if (a[i] == 1 && count % 2 == 0)
            continue;
 
        /* If the bulb's original state is off and count
        is odd, it is currently on...*/
        /* no need to press this switch */
        else if(a[i] == 0 && count % 2 != 0)
            continue;
 
        /* if the bulb's original state is on and count   
        is odd, it is currently off...*/
        /* Press this switch to on the bulb and increase
        the count */
        else if (a[i] == 1 && count % 2 != 0)
        {
            res++;
            count++;
        }
         
        /* if the bulb's original state is off and
        count is even, it is currently off...*/
        /* press this switch to on the bulb and
        increase the count */
        else if (a[i] == 0 && count % 2 == 0)
        {
            res++;
            count++;
        }
    }
    return res;
}
 
// Driver code
int main()
{
    int states[] = {0,1,0,1};
    int n = sizeof(states)/sizeof(states[0]);
   
      // Function Code
    cout << "The minimum number of switches needed are " << bulbs(states,n);
}

// Java program to find number switch presses to
// turn all bulbs on.
import java.util.*;
 
public class GFG
{
    public int bulbs(ArrayList<Integer> a)
    {
        // To keep track of switch presses so far
        int count = 0;
 
        int res = 0;
        for (int i = 0; i < a.size(); i++)
        {
            /* if the bulb's original state is on and count
               is even, it is currently on...*/
            /* no need to press this switch */
            if (a.get(i) == 1 && count%2 == 0)
                continue;
 
            /* If the bulb's original state is off and count
               is odd, it is currently on...*/
            /* no need to press this switch */
            else if(a.get(i) == 0 && count%2 != 0)
                continue;
 
            /* if the bulb's original state is on and count
               is odd, it is currently off...*/
            /* Press this switch to on the bulb and increase
               the count */
            else if (a.get(i) == 1 && count%2 != 0)
            {
                res++;
                count++;
            }
 
            /* if the bulb's original state is off and
               count is even, it is currently off...*/
            /* press this switch to on the bulb and
               increase the count */
            else if (a.get(i) == 0 && count%2 == 0)
            {
                res++;
                count++;
            }
        }
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        GFG gfg = new GFG();
 
        ArrayList<Integer> states = new ArrayList<Integer>();
 
        states.add(0);
        states.add(1);
        states.add(0);
        states.add(1);
 
        System.out.println("The minimum number of switches" +
                           " needed are " + gfg.bulbs(states));
    }
}

# Python program to find number switch presses to
# turn all bulbs on.
 
 
def bulbs(a, n):
    # To keep track of switch presses so far
    count = 0
 
    res = 0
    for i in range(n):
        # if the bulb's original state is on and count
        # is even, it is currently on...
        # no need to press this switch
        if (a[i] == 1 and count % 2 == 0):
            continue
 
        # If the bulb's original state is off and count
        # is odd, it is currently on...
        # no need to press this switch
        elif(a[i] == 0 and count % 2 != 0):
            continue
 
        # if the bulb's original state is on and count
        # is odd, it is currently off...
        # Press this switch to on the bulb and increase
        # the count
        elif (a[i] == 1 and count % 2 != 0):
            res += 1
            count += 1
 
        # if the bulb's original state is off and
        # count is even, it is currently off...
        # press this switch to on the bulb and
        # increase the count
        elif (a[i] == 0 and count % 2 == 0):
            res += 1
            count += 1
    return res
 
 
# Driver code
states = [0, 1, 0, 1]
n = len(states)
print("The minimum number of switches needed are", bulbs(states, n))
 
# This code is contributed by ankush_953

// C# program to find number switch presses
// to turn all bulbs on.
using System;
using System.Collections.Generic;
 
class GFG
{
public virtual int bulbs(List<int> a)
{
    // To keep track of switch presses so far
    int count = 0;
 
    int res = 0;
    for (int i = 0; i < a.Count; i++)
    {
        /* if the bulb's original state is on
        and count is even, it is currently on...*/
        /* no need to press this switch */
        if (a[i] == 1 && count % 2 == 0)
        {
            continue;
        }
 
        /* If the bulb's original state is off
        and count is odd, it is currently on...*/
        /* no need to press this switch */
        else if (a[i] == 0 && count % 2 != 0)
        {
            continue;
        }
 
        /* if the bulb's original state is on
        and count is odd, it is currently off...*/
        /* Press this switch to on the bulb and
        increase the count */
        else if (a[i] == 1 && count % 2 != 0)
        {
            res++;
            count++;
        }
 
        /* if the bulb's original state is off and
        count is even, it is currently off...*/
        /* press this switch to on the bulb and
        increase the count */
        else if (a[i] == 0 && count % 2 == 0)
        {
            res++;
            count++;
        }
    }
    return res;
}
 
// Driver code
public static void Main(string[] args)
{
    GFG gfg = new GFG();
 
    List<int> states = new List<int>();
 
    states.Add(0);
    states.Add(1);
    states.Add(0);
    states.Add(1);
 
    Console.WriteLine("The minimum number of switches" +
                    " needed are " + gfg.bulbs(states));
}
}
 
// This code is contributed by Shrikant13

<script>
// javascript program to find number switch presses to
// turn all bulbs on.
function bulbs(a, n)
{
 
    // To keep track of switch presses so far
    let count = 0;
 
    let res = 0;
    for (let i = 0; i < n; i++)
    {
        /* if the bulb's original state is on and count
        is even, it is currently on...*/
        /* no need to press this switch */
        if (a[i] == 1 && count % 2 == 0)
            continue;
 
        /* If the bulb's original state is off and count
        is odd, it is currently on...*/
        /* no need to press this switch */
        else if(a[i] == 0 && count % 2 != 0)
            continue;
 
        /* if the bulb's original state is on and count   
        is odd, it is currently off...*/
        /* Press this switch to on the bulb and increase
        the count */
        else if (a[i] == 1 && count % 2 != 0)
        {
            res++;
            count++;
        }
         
        /* if the bulb's original state is off and
        count is even, it is currently off...*/
        /* press this switch to on the bulb and
        increase the count */
        else if (a[i] == 0 && count % 2 == 0)
        {
            res++;
            count++;
        }
    }
    return res;
}
 
// Driver code
 
    let states = [0,1,0,1];
    let n = states.length;
    document.write("The minimum number of switches needed are " + bulbs(states,n));
     
    // This code is contributed by vaibhavrabadiya117.
</script>

The minimum number of switches needed are 4

Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)

Este artículo es una contribución de Saloni Baweja . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. 

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.