Given an array of 0 and 1. In how many iterations it is possible that the whole array can be filled with 1's, if in a single iteration immediate neighbours of 1's can be filled.
 
Example 1:
Input:
n = 4
a[] = {1, 0, 1, 0}
Output:
1
Explanation:
Both the 0s has 1 as their immediate neighbour.
So, only one iteration is required to fill the
array with 1.
 
Example 2:
Input:
n = 5
a[] = {0, 0, 1, 0, 0}
Output:
2
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minMoves() which takes the array A[] and its size N as inputs and returns the minimum number of iterations to fill the whole array with 1's (if possible). If it is not possible to fill the array with 1s, return -1 . 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{7}
0 <= A_{i }<= 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

def minMoves( arr, n):
    
    



Solutions:
def minMoves(arr, n):
	max_dist = -1
	last_one = -1
	for i in range(len(arr)):
		if arr[i] == 1:
			if last_one == -1:
				max_dist = i
			else:
				new_dist = i - last_one - 1
				max_dist = max(max_dist, (new_dist - 1) // 2 + 1)
			last_one = i
	if last_one != -1:
		final_dist = n - last_one - 1
		max_dist = max(max_dist, final_dist)
	return -1 if max_dist == -1 else max_dist


def minMoves(arr, n):
	if not 1 in arr:
		return -1
	start = 0
	while start < n and arr[start] == 0:
		start += 1
	end = 0
	while end < n and arr[-end - 1] == 0:
		end += 1
	maxi = 0
	streak = 0
	for i in range(start, n - end):
		if arr[i] == 0:
			streak += 1
		else:
			maxi = max(maxi, streak)
			streak = 0
	return max(start, end, (maxi + 1) // 2)


def minMoves(arr, n):
	if 1 not in arr:
		return -1
	ma = 0
	ind = 0
	for i in range(n):
		if arr[i] == 1:
			ma = i
			ind = i
			break
	st = ind
	for i in range(ind + 1, n):
		if arr[i] == 1:
			ma = max(ma, (i - st) // 2)
			st = i
	ma = max(ma, n - st - 1)
	return ma


def minMoves(arr, n):
	if list(set(arr)) == [0]:
		return -1
	list1 = list()
	index = [i for i in range(n) if arr[i] == 1]
	for i in range(n):
		mini = float('inf')
		for j in index:
			if arr[i] != 1:
				mini = min(mini, abs(j - i))
		if arr[i] != 1:
			list1.append(mini)
	return max(list1)


def minMoves(a, n):
	ans = 0
	temp = 0
	p = -1
	for i in range(n):
		if a[i] == 1:
			if p == -1:
				p = i
				ans = max(ans, temp)
				temp = 0
			else:
				p = i
				ans = max(ans, (temp + 1) // 2)
				temp = 0
		else:
			temp += 1
	ans = max(ans, temp)
	if p == -1:
		return -1
	return ans


def minMoves(arr, n):
	(c, t, p) = (0, 0, -1)
	for i in range(n):
		if arr[i] == 1:
			if p == -1:
				p = i
				c = max(c, t)
				t = 0
			else:
				p = 1
				c = max(c, (t + 1) // 2)
				t = 0
		else:
			t += 1
	c = max(c, t)
	if p == -1:
		c = -1
	return c


def minMoves(arr, n):
	if arr[0] == 1:
		arr[0] = 0
	elif arr[0] == 0:
		arr[0] = -1
	for i in range(1, n):
		if arr[i] == 1:
			arr[i] = 0
		elif arr[i] == 0:
			if arr[i - 1] == -1:
				arr[i] = -1
			else:
				arr[i] = arr[i - 1] + 1
	mx = arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] == 0:
			continue
		elif arr[i + 1] != -1:
			if arr[i] == -1:
				arr[i] = arr[i + 1] + 1
			else:
				arr[i] = min(arr[i], arr[i + 1] + 1)
		mx = max(mx, arr[i])
	return mx


def minMoves(arr, n):
	c = 0
	temp = 0
	prevInd = -1
	for i in range(n):
		if arr[i] == 1:
			if prevInd == -1:
				prevInd = i
				c = max(c, temp)
				temp = 0
			else:
				prevInd = i
				c = max(c, (temp + 1) // 2)
				temp = 0
		else:
			temp += 1
	c = max(c, temp)
	if prevInd == -1:
		c = -1
	return c


def minMoves(arr, n):
	i = 0
	c = 0
	while i < n and arr[i] == 0:
		c += 1
		i += 1
	if c == n:
		return -1
	j = n - 1
	h = 0
	while j >= 0 and arr[j] == 0:
		j -= 1
		h += 1
	d = 0
	e = 0
	for k in range(i, j + 1):
		if arr[k] == 0:
			d += 1
		else:
			if d > e:
				e = d
			d = 0
	return max(c, h, (e + 1) // 2)


def minMoves(arr, n):
	oneFound = False
	res = 0
	i = 0
	while i < n:
		if arr[i] == 1:
			oneFound = True
		while i < n and arr[i] == 1:
			i += 1
		count_zero = 0
		while i < n and arr[i] == 0:
			count_zero += 1
			i += 1
		if oneFound == False and i == n:
			return -1
		curr_count = 0
		if i < n and oneFound == True:
			if count_zero & 1 == 0:
				curr_count = count_zero // 2
			else:
				curr_count = (count_zero + 1) // 2
			count_zero = 0
		else:
			curr_count = count_zero
			count_zero = 0
		res = max(res, curr_count)
	return res


def minMoves(arr, n):
	if arr.count(1) == 0 or arr.count(0) == 0:
		return -1
	else:
		oi = arr.index(1)
		m = 0
		li = oi
		if arr[-1] == 1 and arr[0] == 1:
			for i in range(oi + 1, n):
				if arr[i] == 1:
					m = max(m, i - li)
					li = i
			if m - 1 <= 2:
				return 1
			else:
				return m // 2
		elif arr[-1] == 0 and arr[0] == 1:
			a1 = arr[::-1]
			lii = a1.index(1)
			lii = n - lii - 1
			d = n - lii - 1
			for i in range(oi + 1, n):
				if arr[i] == 1:
					m = max(m, i - li)
					li = i
			if m - 1 <= 2:
				return max(1, d)
			else:
				return max(m // 2, d)
		else:
			a1 = arr[::-1]
			lii = a1.index(1)
			lii = n - lii - 1
			d = n - lii - 1
			for i in range(oi + 1, n):
				if arr[i] == 1:
					m = max(m, i - li)
					li = i
			if m - 1 <= 2:
				return max(1, d, oi)
			else:
				return max(m // 2, d, oi)


def minMoves(arr, n):
	if 1 not in arr:
		return -1
	cost = 0
	zc = 0
	int_max = 0
	first_1 = arr.index(1)
	last_1 = arr[::-1].index(1)
	for i in range(first_1, n - last_1):
		if arr[i] == 0:
			zc += 1
		else:
			if zc % 2 == 0:
				temp = int(zc / 2)
			else:
				temp = int(zc / 2) + 1
			int_max = max(int_max, temp)
			zc = 0
	initial_cost = max(first_1, last_1)
	return max(initial_cost, int_max)


def minMoves(arr, n):
	if list(set(arr)) == [0]:
		return -1
	list1 = []
	index = [i for i in range(n) if arr[i] == 1]
	for i in range(n):
		mini = float('inf')
		for j in index:
			if arr[i] != 1:
				mini = min(mini, abs(j - i))
		if arr[i] != 1:
			list1.append(mini)
	return max(list1)

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		print(minMoves(a, n))
		T -= 1
if __name__ == '__main__':
	main()


def minMoves(arr, n):
	count = 1
	max_count = 0
	for i in range(n - 1):
		if arr[i] == 1 and arr[i + 1] == 0:
			count = 1
		elif arr[i] == 0 and arr[i + 1] == 0:
			count += 1
		elif arr[i] == 0 and arr[i + 1] == 1:
			if count > max_count:
				max_count = count
				count = 0
	if max_count == n or count == n:
		return -1
	count = 0
	if arr[0] == 0:
		for i in range(n):
			if arr[i] == 0:
				count += 1
			else:
				break
		if count * 2 > max_count:
			max_count = count * 2
	count = 0
	if arr[n - 1] == 0:
		for i in range(n - 1, -1, -1):
			if arr[i] == 0:
				count += 1
			else:
				break
		if count * 2 > max_count:
			max_count = count * 2
	return max_count // 2 + max_count % 2


def search(brr, k, length):
	mini = 10 ** 9 + 7
	l = 0
	for i in range(length):
		mini = min(mini, abs(brr[i] - k))
	return mini

def minMoves(arr, n):
	l = []
	for i in range(n):
		if arr[i] == 1:
			l.append(i)
	length = len(l)
	temp_l = []
	if length == 0:
		return -1
	for i in range(n):
		if arr[i] == 1:
			temp_l.append(0)
		else:
			temp_l.append(search(l, i, length))
	return max(temp_l)


def minMoves(arr, n):
	maximum = -1
	ans = 0
	flag = False
	prev = None
	for i in range(0, n):
		if arr[i] == 0:
			ans += 1
		elif prev is None:
			maximum = max(ans, maximum)
			prev = i
		else:
			maximum = max((i - prev) // 2, maximum)
			prev = i
			ans = 0
	ans = 0
	prev = None
	for i in range(n - 1, -1, -1):
		if arr[i] == 0:
			ans += 1
		elif prev is None:
			maximum = max(ans, maximum)
			prev = i
		else:
			maximum = max((prev - i) // 2, maximum)
			prev = i
			ans = 0
	return maximum


import math

def minMoves(arr, n):
	if not 1 in arr:
		return -1
	res = arr.index(1)
	l = res
	i = res + 1
	while i < n:
		if arr[i] == 1:
			numZeros = i - l - 1
			res = max(res, math.ceil(numZeros / 2.0))
			l = i
		i = i + 1
	if arr[-1] == 0:
		res = max(res, n - l - 1)
	return res