Given two arrays switch[], consisting of binary integers denoting whether a switch is ON(0) or OFF(1), and query[], where query[i] denotes the switch to be toggled. The task after completing all the switch toggles is to print the number of times the bulb changes its state, i.e. from ON to OFF or vice-versa.
Examples :
Input: switch[] ={1, 1, 0}, query[] = {3, 2, 1}
Output : 1
Explanation:
Initial state of switches {1, 1, 0}. Since the count of 1’s = 2 (>= ceil(N / 2)), the bulb glows.
query[0] = 3
Next state of switches {1, 1, 1}. Since the count of 1’s = 3 (>= ceil(N / 2)), the bulb glows.
query[1] = 2
Next state of switches {1, 0, 1}. Since the count of 1’s = 2 (>= ceil(N / 2)), the bulb glows.
query[2] = 1
Next state of switches {0, 0, 1}.. Since the count of 1’s = 1 (< ceil(N / 2)), the bulb turns off.
Therefore, the bulb witches from glowing to non-glowing state only once.Input : switch[] = { 1, 1, 0, 0, 1, 1 }
query[] = { 4, 3, 6 }
Output: 0
Approach : Follow the steps below to solve the problem:
- Traverse the array arr[].
- Count the number of 1s to keep track of the initial state of the bulb.
- Traverse the array query[].
- For every query[i], update arr[] and the count of 1s. Check for the current state of the bulb accordingly.
- If the previous and the current states are found to be different, then increment count.
- Finally, print the value of count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of// times a bulb switches its stateint solve(int A[], int n, int Q[], int q){ // Count of 1s int one = 0; // Traverse the array for (int i = 0; i < n; i++) // Update count of 1s if (A[i] == 1) one++; // Update the status of bulb int glows = 0, count = 0; if (one >= ceil(n / 2)) glows = 1; // Traverse the array Q[] for (int i = 0; i < q; i++) { // Stores previous state // of the bulb int prev = glows; // Toggle the switch and // update count of 1s if (A[Q[i] - 1] == 1) one--; if (A[Q[i] - 1] == 0) one++; A[Q[i] - 1] ^= 1; if (one >= ceil(n / 2.0)) { glows = 1; } else { glows = 0; } // If the bulb switches state if (prev != glows) count++; } // Return count return count;}// Driver Codeint main(){ // Input int n = 3; int arr[] = { 1, 1, 0 }; int q = 3; // Queries int Q[] = { 3, 2, 1 }; // Function call to find number // of times the bulb toggles cout << solve(arr, n, Q, q); return 0;}// This code is contributed by splevel62. |
Java
// Java implementation of// the above approachimport java.util.*;public class Main { // Function to find the number of // times a bulb switches its state static int solve(int[] A, int n, int Q[], int q) { // Count of 1s int one = 0; // Traverse the array for (int i = 0; i < n; i++) // Update count of 1s if (A[i] == 1) one++; // Update the status of bulb int glows = 0, count = 0; if (one >= (int)Math.ceil(n / 2)) glows = 1; // Traverse the array Q[] for (int i = 0; i < q; i++) { // Stores previous state // of the bulb int prev = glows; // Toggle the switch and // update count of 1s if (A[Q[i] - 1] == 1) one--; if (A[Q[i] - 1] == 0) one++; A[Q[i] - 1] ^= 1; if (one >= (int)Math.ceil(n / 2.0)) { glows = 1; } else { glows = 0; } // If the bulb switches state if (prev != glows) count++; } // Return count return count; } // Driver Code public static void main(String args[]) { // Input int n = 3; int arr[] = { 1, 1, 0 }; int q = 3; // Queries int Q[] = { 3, 2, 1 }; // Function call to find number // of times the bulb toggles System.out.println( solve(arr, n, Q, q)); }} |
Python3
# Python program for # the above approachimport math# Function to find the number of# times a bulb switches its statedef solve(A, n, Q, q): # count of 1's one = 0 # Traverse the array for i in range(0, n): # update the array if (A[i] == 1): one += 1 # update the status of bulb glows = 0 count = 0 if (one >= int(math.ceil(n / 2))): glows = 1 # Traverse the array Q[] for i in range(0, q): # stores previous state of # the bulb prev = glows # Toggle the switch and # update the count of 1's if (A[Q[i] - 1] == 1): one -= 1 if (A[Q[i] - 1] == 0): one += 1 A[Q[i] - 1] ^= 1 if (one >= int(math.ceil(n/2.0))): glows = 1 else: glows = 0 # if the bulb switches state if (prev != glows): count += 1 # Return count return count# Driver code# Inputn = 3arr = [1, 1, 0]q = 3# QueriesQ = [3, 2, 1]# Function call to find number# of times the bulb togglesprint(solve(arr, n, Q, q))# This code id contributed by Virusbuddah |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the number of // times a bulb switches its state static int solve(int[] A, int n, int[] Q, int q) { // Count of 1s int one = 0; // Traverse the array for (int i = 0; i < n; i++) // Update count of 1s if (A[i] == 1) one++; // Update the status of bulb int glows = 0, count = 0; if (one >= (int)Math.Ceiling((double)n / 2)) glows = 1; // Traverse the array Q[] for (int i = 0; i < q; i++) { // Stores previous state // of the bulb int prev = glows; // Toggle the switch and // update count of 1s if (A[Q[i] - 1] == 1) one--; if (A[Q[i] - 1] == 0) one++; A[Q[i] - 1] ^= 1; if (one >= (int)Math.Ceiling((double)n / 2.0)) { glows = 1; } else { glows = 0; } // If the bulb switches state if (prev != glows) count++; } // Return count return count; } // Driver Code static public void Main () { // Input int n = 3; int[] arr = { 1, 1, 0 }; int q = 3; // Queries int[] Q = { 3, 2, 1 }; // Function call to find number // of times the bulb toggles Console.WriteLine( solve(arr, n, Q, q)); }}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// Javascript program for the above approach// Function to find the number of// times a bulb switches its statefunction solve(A, n, Q, q){ // Count of 1s var one = 0; // Traverse the array for (var i = 0; i < n; i++) // Update count of 1s if (A[i] == 1) one++; // Update the status of bulb var glows = 0, count = 0; if (one >= Math.ceil(n / 2)) glows = 1; // Traverse the array Q[] for (var i = 0; i < q; i++) { // Stores previous state // of the bulb var prev = glows; // Toggle the switch and // update count of 1s if (A[Q[i] - 1] == 1) one--; if (A[Q[i] - 1] == 0) one++; A[Q[i] - 1] ^= 1; if (one >= Math.ceil(n / 2.0)) { glows = 1; } else { glows = 0; } // If the bulb switches state if (prev != glows) count++; } // Return count return count;}// Driver Code// Inputvar n = 3;var arr = [1, 1, 0];var q = 3;// Queriesvar Q = [3, 2, 1];// Function call to find number// of times the bulb togglesdocument.write( solve(arr, n, Q, q));// This code is contributed by noob2000.</script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
