There are N rooms in a straight line in Geekland State University's hostel, you are given a binary string S of length N where S[i] = '1' represents that there is a wifi in i^{th} room or S[i] = '0' represents no wifi. Each wifi has range X i.e. if there is a wifi in i^{th} room then its range will go upto X more rooms on its left as well as right. You have to find whether students in all rooms can use wifi.
Example 1: 
Input:
N = 3, X = 0
S = "010"
Output:
0
Explanation: 
Since the range(X)=0, So Wifi is only 
accessible in second room while 1st & 3rd
room have no wifi.
Example 2: 
Input:
N = 5, X = 1
S = "10010"
Output:
1
Explanation: 
Index 0 : Wifi is available
Index 1 : Since range of 0th Index is 1
          so, here wifi will be available.
Index 2 : Since range of 3rd Index is 1
          so, here also wifi available.
Index 3 : Wifi is available
Index 4 : here range of 3rd Index is available.
So all the rooms have wifi, so return true.
Your Task:
You don't need to read input or print anything. Your task is to complete the function wifiRange( ) which takes integer N, string S and integer X as input parameters and returns true if students in all rooms can use wifi or false otherwise.
Expected Time Complexity:O(N)
Expected Space Complexity:O(1)
Constraints:
1 ≤ N ≤ 10^{6}
0 ≤ X ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def wifiRange(self, N, S, X): 

        #code here

Solutions:
class Solution:

	def wifiRange(self, N, S, X):
		n = X
		notFound = True
		for i in S:
			if notFound and n < 0:
				return 0
			if notFound == False and n < -X:
				return 0
			if i == '0':
				n = n - 1
			else:
				n = X
				notFound = False
			N = N - 1
			if N <= 0 and n < 0:
				return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		visit = [0] * N
		for i in range(0, N):
			if S[i] == '1':
				visit[max(i - X, 0)] += 1
				if i + X + 1 < N:
					visit[i + X + 1] += -1
		for i in range(1, N):
			visit[i] += visit[i - 1]
		for val in visit:
			if val == 0:
				return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		i = 0
		while i < N:
			canStudentAccessWiFi = 1
			if S[i] == '1':
				i += 1
			elif S[i] == '0':
				canStudentAccessWiFi = 0
				leftSteps = 0
				while i - leftSteps - 1 >= 0 and leftSteps < X:
					if S[i - leftSteps - 1] == '1':
						canStudentAccessWiFi = 1
						break
					else:
						leftSteps += 1
				if canStudentAccessWiFi != 1:
					rightSteps = 0
					while i + rightSteps + 1 < N and rightSteps < X:
						if S[i + rightSteps + 1] == '1':
							canStudentAccessWiFi = 1
							break
						else:
							rightSteps += 1
			if canStudentAccessWiFi == 0:
				return False
			else:
				i += 1
		return True


class Solution:

	def wifiRange(self, N, S, X):
		current_range = 0
		for i in S:
			if i == '0':
				current_range -= 1
				if current_range < -X:
					return False
			else:
				current_range = X
		if current_range < 0:
			return False
		return True


class Solution:

	def wifiRange(self, n, s, x):
		l = 0
		for i in range(n):
			if s[i] == '0':
				l += 1
			if s[i] == '1':
				l = -x
			if l > x:
				return False
		if l > 0:
			return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		l = 0
		for i in range(N):
			if S[i] == '0':
				l += 1
			if S[i] == '1':
				l = -X
			if l > X:
				return False
		if l > 0:
			return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		stack = []
		for i in range(N):
			if S[i] == '1':
				while stack and stack[-1][0] == 0 and (i - stack[-1][1] <= X):
					stack.pop()
				stack.append((1, i))
			elif stack and stack[-1][0] == 1 and (i - stack[-1][1] <= X):
				continue
			else:
				stack.append((0, i))
		ans = len(stack)
		for (ty, ind) in stack:
			if ty == 1:
				ans -= 1
		return ans == 0


class Solution:

	def wifiRange(self, N, S, X):
		a = list(map(int, list(S)))
		(left, right) = (0, 0)
		for i in range(N):
			if a[i] == 1:
				left = X
			elif left > 0:
				(a[i], left) = (1, left - 1)
			if a[-(i + 1)] == 1:
				right = X
			elif right > 0:
				(a[-(i + 1)], right) = (1, right - 1)
		return 0 if 0 in a else 1


class Solution:

	def wifiRange(self, N, S, X):
		frst_wifi = 0
		last_wifi = N - 1
		while S[frst_wifi] != '1':
			if frst_wifi >= X:
				return 0
			frst_wifi += 1
		while S[last_wifi] != '1':
			if N - 1 - last_wifi >= X:
				return 0
			last_wifi -= 1
		room = frst_wifi + 1
		rng = 2 * X
		tol = 1
		while room < last_wifi:
			if S[room] == '1':
				tol = 0
			if tol > rng:
				return 0
			else:
				tol += 1
			room += 1
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		arr = [0] * N
		for i in range(N):
			if S[i] == '1':
				left = max(i - X, 0)
				arr[left] += 1
				if i + X + 1 < N:
					arr[i + X + 1] -= 1
		for i in range(1, N):
			arr[i] += arr[i - 1]
		for i in arr:
			if i <= 0:
				return 0
		return 1


class Solution:

	def wifiRange(self, n, s, x):
		s = list(s)
		wifi_range = 0
		for i in range(n):
			if s[i] == '1':
				wifi_range = x
			else:
				if s[i] == '0' and wifi_range > 0:
					s[i] = 'F'
				wifi_range -= 1
		wifi_range = 0
		for i in range(n - 1, -1, -1):
			if s[i] == '1':
				wifi_range = x
			else:
				if s[i] == '0' and wifi_range > 0:
					s[i] = 'F'
				wifi_range -= 1
		for i in range(n):
			if s[i] == '0':
				return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		li = list(S)
		st = '0' * (X + 1)
		mid = '0' * (2 * X + 1)
		if mid in S:
			return 0
		elif S[:X + 1] == st or S[N - X - 1:] == st:
			return 0
		else:
			return 1


class Solution:

	def wifiRange(self, N, S, X):
		S = list(S)
		wifi_range = 0
		for i in range(N):
			if S[i] == '1':
				wifi_range = X
			else:
				if S[i] == '0' and wifi_range > 0:
					S[i] = 'F'
				wifi_range -= 1
		wifi_range = 0
		for i in range(N - 1, -1, -1):
			if S[i] == '1':
				wifi_range = X
			else:
				if S[i] == '0' and wifi_range > 0:
					S[i] = 'F'
				wifi_range -= 1
		for i in range(N):
			if S[i] == '0':
				return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		for i in range(N):
			wifi_found = False
			for j in range(max(0, i - X), min(N, i + X + 1)):
				if S[j] == '1':
					wifi_found = True
					break
			if not wifi_found:
				return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		ct = 0
		ans = [0] * N
		s = S
		for i in range(N):
			if ct > 0:
				ans[i] = 1
				ct -= 1
			if s[i] == '1':
				ct = X
				ans[i] = 1
		ct = 0
		for i in range(N - 1, -1, -1):
			if ct > 0:
				ans[i] = 1
				ct -= 1
			if s[i] == '1':
				ct = X
		if ans.count(1) == N:
			return 1
		return 0


class Solution:

	def wifiRange(self, N, S, X):
		count = 0
		tmp = 0
		for i in range(len(S)):
			if S[i] == '0':
				count -= 1
			else:
				count += X
				if count < 0:
					tmp += abs(count)
					count = X
				else:
					count = X
		if count < 0:
			tmp += abs(count)
		if tmp > 0:
			return False
		else:
			return True


class Solution:

	def wifiRange(self, N, S, X):
		t = 0
		y = S.count('1')
		for i in range(N):
			if S[i] == '0':
				if t == X:
					return 0
				else:
					t += 1
			elif y - 1 > 0:
				y -= 1
				t = -X
			else:
				t = 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		s = [i for i in S]
		i = 0
		while i < N:
			(left, right) = (i - 1, i + 1)
			if s[i] == '1':
				(x1, x2) = (X, X)
				while left >= 0 and x1 > 0:
					if s[left] == '1':
						break
					s[left] = '1'
					left -= 1
					x1 -= 1
				while right < N and x2 > 0:
					if s[right] == '1':
						break
					else:
						s[right] = '1'
						right += 1
						x2 -= 1
			i = right
		return '0' not in s


class Solution:

	def wifiRange(self, N, S, X):
		cnt = []
		for i in range(N):
			if S[i] == '1':
				cnt.append(i)
		n = len(cnt)
		if cnt[0] > X:
			return 0
		if N - cnt[n - 1] - 1 > X:
			return 0
		for i in range(n - 1):
			ans = cnt[i + 1] - cnt[i] - 1
			if ans > 2 * X:
				return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		right = -1
		left = -1
		j = X
		for i in range(X):
			if S[i] == '1':
				right = i
		i = 0
		while i < len(S):
			flag = 0
			if i > 0:
				if S[i - 1] == '1':
					left = i - 1
			if j < len(S) and S[j] == '1':
				right = j
			if S[i] == '1':
				flag = 1
				i += 1
				j += 1
				continue
			if S[i] == '0':
				if left >= 0:
					if i - left <= X:
						flag = 1
				if right >= 0:
					if right > i and right - i <= X:
						flag = 1
			i += 1
			j += 1
			if flag == 0:
				return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		index = -1
		for i in range(N):
			if S[i] == '1':
				index = i
				break
		if index == -1:
			return 0
		if X < index:
			return 0
		i = index + 1
		while i < N:
			if S[i] == '1':
				ele = i - index - 1
				if 2 * X < ele:
					return 0
				index = i
			i += 1
		if S[-1] == '0':
			if X < N - index - 1:
				return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		start = 1
		end = N - 1
		first = True
		for i in range(N):
			if S[i] == '1':
				s = i - X
				e = i + X
				if first == True:
					start = s
					first = False
				if s <= end + 1:
					end = e
		if start <= 0 and end >= N - 1:
			return True
		return False


class Solution:

	def wifiRange(self, N, S, X):
		wifi = 0
		for w in S:
			if w == '0':
				wifi += 1
			else:
				if wifi > X:
					return 0
				wifi = -X
		if wifi > 0:
			return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		s = list(S)
		for i in range(0, len(s)):
			if s[i] == '0':
				if i == '0':
					if '1' not in s[1:i + X + 1]:
						return 0
				elif i == len(s):
					if '1' not in s[i - X:i]:
						return 0
				else:
					a = i - X
					b = i + X
					if a < 0:
						a = 0
					if b >= len(s):
						b = len(s) - 1
					if '1' not in s[i + 1:b + 1] and '1' not in s[a:i]:
						return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		v = []
		for i in range(N):
			if S[i] == '1':
				v.append(i)
		for i in range(len(v) - 1):
			if v[i + 1] - v[i] - 1 > 2 * X:
				return False
		if v[0] > X:
			return False
		if N - 1 - v[len(v) - 1] > X:
			return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		if X > N:
			return True
		sList = list(S)
		sBool = [int(x) for x in sList]
		for (idx, i) in enumerate(sBool):
			if not i and (not self.inRange(idx, sBool, X, N)):
				return False
		return True

	def inRange(self, index, S, X, N):
		start = index - X if index - X >= 0 else 0
		end = index + X + 1 if index + X + 1 <= N else N
		return any(S[start:end])


class Solution:

	def wifiRange(self, N, S, X):
		left = [-1] * N
		right = [-1] * N
		last_wifi = -1
		for i in range(N):
			if S[i] == '1':
				last_wifi = i
			left[i] = last_wifi
		last_wifi = -1
		for i in range(N - 1, -1, -1):
			if S[i] == '1':
				last_wifi = i
			right[i] = last_wifi
		for i in range(N):
			left_dist = float('inf') if left[i] == -1 else i - left[i]
			right_dist = float('inf') if right[i] == -1 else right[i] - i
			if left_dist > X and right_dist > X:
				return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		c = 0
		max = 0
		for i in S:
			if i == '1':
				c = 0
			else:
				c += 1
				if c > max:
					max = c
		if S[0] == '0':
			if '1' in S[1:X + 1]:
				None
			else:
				return 0
		if S[-1] == '0':
			if '1' in S[-2:-2 - X:-1]:
				None
			else:
				return 0
		a = max
		if int(a) > 2 * X:
			return 0
		else:
			return 1


class Solution:

	def wifiRange(self, N, S, X):
		position = 0
		flag = True
		for index in range(N):
			if int(S[index]) == 1:
				if position >= index - X:
					position = index + X + 1
				else:
					flag = False
					break
		val = position >= N
		if not flag:
			return 0
		elif val:
			return 1


class Solution:

	def wifiRange(self, N, S, X):
		i = 0
		while i < N:
			if S[i] == '1':
				first_one = i
				if i > X:
					return 0
				break
			i += 1
		current_one = first_one
		i = current_one + 1
		while i < N:
			if S[i] == '1':
				diff = i - current_one - 1
				if diff > 2 * X:
					return 0
				current_one = i
			i += 1
		if N - current_one - 1 > X:
			return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		ran = 0
		for i in range(N):
			if S[i] == '1':
				ran = X
			else:
				ran -= 1
			if ran < -X:
				return False
		if ran < 0:
			return False


class Solution:

	def wifiRange(self, N, S, X):
		rang = 0
		for i in range(len(S)):
			if S[i] == '1':
				rang = X
			else:
				rang -= 1
			if rang < -X:
				return False
		if rang < 0:
			return False
		else:
			return True


class Solution:

	def wifiRange(self, N, S, X):
		st = 0
		while st < N and S[st] != '1':
			st += 1
		if st == N or st > X:
			return False
		last = st
		for i in range(st, N):
			if i - last + 1 > 2 * (X + 1):
				return False
			if S[i] == '1':
				last = i
		if N - last > X + 1:
			return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		wifi_range = 0
		for i in range(N):
			if S[i] == '1':
				if abs(wifi_range) > X:
					return 0
				wifi_range = X
			else:
				wifi_range -= 1
		if wifi_range >= 0:
			return 1
		else:
			return 0


class Solution:

	def length1(x):
		return len(x)

	def wifiRange(self, N, S, X):
		count = 0
		for i in range(0, len(S)):
			if S[i] == '1':
				count += 1
			else:
				x = S[i:i + X + 1]
				y = S[i - X:i + 1]
				if S[i:i + X + 1].count('1') != 0:
					count += 1
				elif S[i - X:i + 1].count('1') != 0:
					count += 1
				elif y == '':
					if S[0:i + 1].count('1') != 0:
						count += 1
				elif x == '':
					if S[i:].count('1') != 0:
						count += 1
		return count == N


class Solution:

	def wifiRange(self, N, S, X):
		i = 0
		while i < N:
			if S[i] == '0':
				wifi_position = self.findCoverage(i, S, X)
				if wifi_position < 0:
					return False
				i = wifi_position
			if S[i] == '1':
				wifi_position = self.findCoverage(i, S, X)
				if wifi_position < 0:
					i += X + 1
				else:
					i = wifi_position
		return True

	def findCoverage(self, position, S, X):
		end_index = min(position + X, len(S) - 1)
		for i in range(end_index, position, -1):
			if S[i] == '1':
				return i
		return -1


class Solution:

	def wifiRange(self, N, S, X):
		ones = 0
		zeros = 0
		for i in range(N):
			if S[i] == '0':
				zeros += 1
				continue
			if S[i] == '1':
				ones += 1
				if zeros > X * ones:
					return False
				zeros = 0
				ones = 1
		if zeros > X * ones:
			return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		ones = 0
		zero = 0
		for i in S:
			if i == '0' and ones == 0:
				zero += 1
				if zero > X:
					return 0
			elif i == '1':
				ones = 1
			if ones != 0:
				if i == '0':
					zero += 1
				else:
					if zero > 2 * X:
						return 0
					zero = 0
		if zero > X:
			return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		lst = []
		for i in range(N):
			if S[i] == '1':
				lst.append(i)
		if lst[0] > X or N - lst[-1] - 1 > X:
			return 0
		n = len(lst)
		for i in range(n - 1):
			if lst[i + 1] - lst[i] - 1 > 2 * X:
				return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		l = list(map(int, S))
		newlist = []
		for i in range(len(l)):
			newlist.append(0)
		current_range = 0
		for i in range(len(l)):
			if l[i] == 1:
				current_range = X
				newlist[i] += X + 1
			elif current_range == 0:
				newlist[i] += 0
			elif current_range > 0:
				newlist[i] += current_range
				current_range -= 1
		l = l[::-1]
		newlist = newlist[::-1]
		for i in range(len(l)):
			if l[i] == 1:
				current_range = X
				newlist[i] += X + 1
			elif current_range == 0:
				newlist[i] += 0
			elif current_range > 0:
				newlist[i] += current_range
				current_range -= 1
		if newlist.count(0) == False:
			return True
		else:
			return


class Solution:

	def wifiRange(self, N, S, X):
		t = '0' * (X + 1)
		if S[:len(t)] == t or S[-len(t):] == t:
			return False
		t = '0' * (2 * X + 1)
		if S.find(t) != -1:
			return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		zero = 0
		one = 0
		for i in range(N):
			if S[i] == '1':
				if zero > 0:
					if one == 0 and zero > X:
						return False
					elif zero > 2 * X:
						return False
				zero = 0
				one = 1
			else:
				zero += 1
		if zero > 0:
			if one == 0 or zero > X:
				return False
		return True


class Solution:

	def wifiRange(self, N, S, X):
		flag = 0
		count1 = 0
		count2 = 0
		count = 1
		if S[0] == '0':
			j = 0
			while S[j] == '0':
				count1 = count1 + 1
				j = j + 1
		if S[N - 1] == '0':
			j = N - 1
			while S[j] == '0':
				count2 = count2 + 1
				j = j - 1
		if count2 > X or count1 > X:
			flag = 1
		else:
			for i in range(N):
				if i + 1 < N:
					if S[i] == '0' and S[i + 1] == '0':
						count = count + 1
					else:
						count = 1
					if count > 2 * X:
						flag = 1
		if flag == 1:
			return 0
		else:
			return 1


class Solution:

	def wifiRange(self, N, S, X):
		r = 0
		count = 0
		for i in range(N):
			if S[i] == '1':
				count += 1
				if i - r - 1 > 2 * X:
					return 0
				r = i
			if count == 1:
				if r > X:
					return 0
		if N - r - 1 > X:
			return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		S = '0' * X + S + '0' * X
		i = 0
		while i < len(S):
			c = 0
			while i < len(S) and S[i] != '1':
				c += 1
				i += 1
			if c > 2 * X:
				return 0
			i += 1
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		count = 0
		k = 2 * X + 1
		j = 0
		l = 0
		for i in range(N):
			j = i
			if int(S[i]) == 0:
				count += 1
				if count == X + 1:
					return False
			else:
				count = 0
				break
		for i in range(N - 1, -1, -1):
			l = i
			if int(S[i]) == 0:
				count += 1
				if count == X + 1:
					return False
			else:
				count = 0
				break
		for i in range(j, l + 1):
			if int(S[i]) == 0:
				count += 1
				if count == k:
					return False
			else:
				count = 0
		return True


class Solution:

	def wifiRange(self, N, S, X):
		if S[0] == '0' and '1' not in S[0:X + 1]:
			return 0
		for i in range(1, N):
			if S[i] == '0':
				if '1' not in S[i:i + X + 1]:
					if i - X < 0 and '1' not in S[0:i]:
						return 0
					elif i - X >= 0 and '1' not in S[i - X:i]:
						return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		lst = [int(i) for i in list(S)]
		cnt = 0
		for i in range(N):
			if lst[i] == 1:
				if cnt == 0:
					start = max(0, i - X)
					if start != 0:
						return 0
					end = min(N - 1, i + X)
				else:
					new_start = max(0, i - X)
					new_end = min(N - 1, i + X)
					if new_start - end > 1:
						return 0
					end = new_end
				cnt += 1
		if start == 0 and end == N - 1:
			return 1
		else:
			return 0


class Solution:

	def wifiRange(self, N, S, X):
		count = X
		for i in range(N):
			if S[i] == '0':
				count += 1
			if S[i] == '1':
				count = 0
			if count > X * 2:
				return False
		return True if count <= X else False


class Solution:

	def wifiRange(self, N, S, X):
		listy = [False] * N
		for i in range(N):
			num = S[i]
			if num == '1':
				start = i - X if i - X > 0 else 0
				end = i + X + 1 if i + X + 1 < N else N
				listy[start:end] = [True] * (end - start)
			elif not listy[i]:
				listy[i] = False
		return all(listy)


class Solution:

	def wifiRange(self, N, S, X):
		prev = -1 - X
		for (i, c) in enumerate(S):
			if c == '1':
				prev = i
			if prev + 2 * X < i:
				return 0
		if prev + X < N - 1:
			return 0
		return 1


class Solution:

	def wifiRange(self, N, S, X):
		c = [0] * N
		for i in range(N):
			if S[i] == '1':
				start = max(0, i - X)
				end = min(N, i + X + 1)
				c[start:end] = [1] * (end - start)
		if 0 in c:
			return 0
		else:
			return 1


class Solution:

	def wifiRange(self, N, S, X):
		visited = [0] * N
		for i in range(N):
			if S[i] == '1':
				visited[max(i - X, 0)] += 1
				if i + X + 1 < N:
					visited[i + X + 1] += -1
		for i in range(1, N):
			visited[i] += visited[i - 1]
		return all(visited)


class Solution:

	def wifiRange(self, N, S, X):
		previous = -1
		for i in range(N):
			if S[i] == '1':
				temp = i - X
				if temp - previous > 1:
					return 0
				previous = i + X
		if previous < N - 1:
			return 0
		return 1