N light bulbs are connected by a wire. Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb. Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. "0 represents the bulb is off and 1 represents the bulb is on."
 
Example 1:
Input:
N=4
arr[] = { 0, 0, 0, 0 }
Output:  1
Explanation: 
From the given set of bulbs change
the state of the first bulb from off
to on ,which eventually turn the rest
three bulbs on the right of it.
Example 2:
Input:
N=4
arr[] = { 1, 0, 0, 1 }
Output:  2
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function countFlips() that takes array A and integer N as parameters and returns the minimum number of press required to turn on all the bulbs.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def countFlips(self,a,n):

        #code here





Solutions:
class Solution:

	def countFlips(self, a, n):
		count = 0
		for i in range(n):
			if a[i] == 1 and count % 2 == 0:
				continue
			elif a[i] == 0 and count % 2 != 0:
				continue
			elif a[i] == 1 and count % 2 != 0:
				count += 1
			elif a[i] == 0 and count % 2 == 0:
				count += 1
		return count


class Solution:

	def countFlips(self, a, n):
		i = 0
		while i < n and a[i]:
			i += 1
		if i == n:
			return 0
		count = 1
		for i in range(i, n - 1):
			count += a[i] != a[i + 1]
		return count


class Solution:

	def countFlips(self, a, n):
		cost = 0
		for i in range(n):
			if cost % 2 == 1:
				a[i] = not a[i]
			if a[i] == 0:
				cost += 1
		return cost


class Solution:

	def countFlips(self, a, n):
		count = 0
		for i in a:
			if count % 2 == 0:
				i = i
			else:
				i = not i
			if i % 2 == 1:
				continue
			else:
				count += 1
		return count


class Solution:

	def countFlips(self, a, n):
		summ = 0
		for i in range(n):
			if a[i] == 0:
				if summ % 2 == 0:
					summ += 1
			elif a[i] == 1:
				if summ % 2 == 1:
					summ += 1
		return summ


class Solution:

	def countFlips(self, a, n):
		cost = 0
		for b in a:
			if cost % 2 == 0:
				b = b
			else:
				b = not b
			if b % 2 == 1:
				continue
			else:
				cost += 1
		return cost


class Solution:

	def countFlips(self, mat, n):
		mat = mat[::-1]
		c = 0
		for i in range(1, n):
			if mat[i - 1] != mat[i]:
				c += 1
		if mat[-1] == 0:
			c += 1
		return c


class Solution:

	def countFlips(self, a, n):
		count = 0
		for i in range(n - 1):
			if a[i] != a[i + 1]:
				count += 1
		if a[0] == 0:
			return count + 1
		else:
			return count


class Solution:

	def countFlips(self, a, n):
		flip = 0
		for i in a:
			if i == 0 and flip % 2 == 0:
				flip += 1
			elif i == 1 and flip % 2 != 0:
				flip += 1
		return flip


class Solution:

	def countFlips(self, a, n):
		(z, o) = (0, 0)
		one = 1
		for i in range(n):
			if a[i] == 0:
				z += 1
			else:
				o += 1
		c = 0
		for i in range(n):
			if a[i] == one:
				o -= 1
				continue
			z -= 1
			(o, z) = (z, o)
			c += 1
			if one == 0:
				one = 1
			else:
				one = 0
		return c


class Solution:

	def countFlips(self, a, n):
		c = 0
		for i in a:
			if c % 2 != 0:
				i = int(not i)
			if i == 0:
				c += 1
		return c


class Solution:

	def countFlips(self, a, n):
		i = 0
		c = 0
		k = False
		while i < n:
			if a[i] == k:
				c += 1
				k = not k
				i += 1
			else:
				i += 1
		return c


class Solution:

	def countFlips(self, a, n):
		ans = 0
		state = 0
		for i in range(n):
			if a[i] == state:
				ans += 1
				state = 1 - state
		return ans


class Solution:

	def countFlips(self, a, n):
		i = 0
		count = 0
		while i < n:
			if a[i] == 0 and count % 2 == 0:
				count += 1
			elif a[i] == 1 and count % 2 == 1:
				count += 1
			i += 1
		return count


class Solution:

	def countFlips(self, a, n):
		c = 0
		for i in range(0, n):
			if c % 2 == 0 and a[i] == 0:
				c += 1
			if c % 2 != 0 and a[i] == 1:
				c += 1
		return c


class Solution:

	def countFlips(self, a, n):
		flag = False
		cost = 0
		for i in range(n):
			if not flag:
				if a[i] == 0:
					cost += 1
					flag = not flag
				else:
					continue
			elif a[i] == 1:
				cost += 1
				flag = not flag
		return cost


class Solution:

	def countFlips(self, a, n):
		count = 0
		result = 0
		for i in range(n):
			if a[i] == 0 and count % 2 == 0:
				count += 1
				result += 1
			elif a[i] == 1 and count % 2 != 0:
				count += 1
				result += 1
			elif a[i] == 0 and count % 2 != 0:
				continue
			elif a[i] == 1 and count % 2 == 0:
				continue
		return result
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	print(ob.countFlips(a, n))


class Solution:

	def countFlips(self, a, n):
		cc = 0
		switch = 0
		for i in range(n):
			if a[i] == switch:
				if a[i] == 1:
					switch = 0
				else:
					switch = 1
				cc += 1
		return cc


class Solution:

	def countFlips(self, a, n):
		count = 0
		for i in a:
			if not count & 1:
				if i == 0:
					count += 1
			elif i == 1:
				count += 1
		return count


class Solution:

	def countFlips(self, a, n):
		cost = 0
		switch = 1
		for i in a:
			if i != switch:
				cost += 1
				switch = 1 - switch
		return cost


class Solution:

	def countFlips(self, a, n):
		f = True
		cost = 0
		for i in a:
			if i == 0 and f or (i == 1 and (not f)):
				cost += 1
				f = not f
		return cost


class Solution:

	def countFlips(self, a, n):
		cnt = 0
		if a[0] == 0:
			cnt += 1
		for i in range(1, n):
			if a[i] != a[i - 1]:
				cnt += 1
		return cnt


class Solution:

	def countFlips(self, a, n):
		ans = 0
		last = 1
		for x in a:
			if x != last:
				ans += 1
				last = x
		return ans


class Solution:

	def countFlips(self, a, n):
		num = 0
		i = 0
		while i < n and a[i] == 1:
			i += 1
		if i < n:
			x = a[i]
		else:
			return 0
		while i < n:
			if x != a[i]:
				x = a[i]
				num += 1
			i += 1
		return num + 1


class Solution:

	def countFlips(self, a, n):
		count = []
		sofar = 1
		for i in range(1, n):
			if a[i] == a[i - 1]:
				sofar += 1
			else:
				count.append(sofar)
				sofar = 1
		count.append(sofar)
		ans = len(count)
		if a[0] == 1:
			return ans - 1
		return ans


class Solution:

	def countFlips(self, a, n):
		flag = 0
		count = 0
		for i in range(n):
			if a[i] == flag:
				flag = (flag + 1) % 2
				count += 1
		return count


class Solution:

	def countFlips(self, a, n):
		res = 0
		for j in range(n - 1, 0, -1):
			if a[j] != a[j - 1]:
				res += 1
		if a[0] == 0:
			res += 1
		return res


class Solution:

	def countFlips(self, a, n):
		s = 0
		for i in range(n):
			if s % 2 == 0:
				curr_state = a[i]
			else:
				curr_state = 1 - a[i]
			if curr_state == 0:
				s += 1
		return s


class Solution:

	def countFlips(self, a, n):
		c = 0
		flg = 0
		sw = 1
		for i in range(n):
			if sw ^ a[i] == 0:
				pass
			elif sw ^ a[i] == 1:
				c += 1
				sw = a[i]
		return c