Geek is in a geekland which have a river and some stones in it. Initially geek can step on any stone. Each stone has a number on it representing the value of exact step geek can move. If the number is +ve then geeks can move right and if the number is -ve then geeks can move left. Bad Stones are defined as the stones in which if geeks steps, will reach a never ending loop whereas good stones are the stones which are safe from never ending loops. Return the number of good stones in river.
Example 1:
Input: [2, 3, -1, 2, -2, 4, 1]
Output: 3
Explanation: Index 3, 5 and 6 are safe only. As index 1, 4, 2 forms a cycle and from index 0 you can go to index 2 which is part of cycle.
Example 2:
Input: [1, 0, -3, 0, -5, 0]
Output: 2
Explanation: Index 2 and 4 are safe only. As index 0, 1, 3, 5 form cycle.
Your Task:
You don't need to read input or print anything. Your task is to complete the function badStones() which takes integer n and an array arr as input, and return an interger value as the number of good stones. Here n is the lenght of arr.
Expected Time Complexity : O(N), N is the number of stones
Expected Auxiliary Space : O(N), N is the number of stones
Constraints:
   1 <= n < 10^5 (where n is the length of the array)
  -1000 <= arr[i] < 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Graph algorithms

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def goodStones(self, n, arr) -> int:

        #code here

Solutions:
def fun(i, n, arr, visit):
	if i < 0 or i >= n:
		return 2
	if visit[i] == 1:
		return visit[i]
	visit[i] = 1
	visit[i] = fun(i + arr[i], n, arr, visit)
	return visit[i]

class Solution:

	def goodStones(self, n, arr) -> int:
		visit = [0] * n
		ans = 0
		for i in range(n):
			if visit[i] == 0:
				visit[i] = fun(i, n, arr, visit)
		for i in range(n):
			if visit[i] == 2:
				ans += 1
		return ans


class Solution:

	def goodStones(self, n, arr) -> int:
		good = set()
		bad = set()
		for node in range(n):
			if node in good or node in bad:
				continue
			visited = set()
			while True:
				if node in good or node >= n or node < 0:
					good.update(visited)
					break
				if node in visited or node in bad:
					bad.update(visited)
					break
				visited.add(node)
				node += arr[node]
		return len(good)


class Solution:

	def search_stones(self, curr_index, arr, stepped, n):
		if curr_index < 0 or curr_index >= n:
			return True
		if stepped[curr_index] is not None:
			return stepped[curr_index]
		stepped[curr_index] = False
		stepped[curr_index] = self.search_stones(curr_index + arr[curr_index], arr, stepped, n)
		return stepped[curr_index]

	def goodStones(self, n, arr) -> int:
		stepped = [None] * n
		answer = 0
		for i in range(n):
			if self.search_stones(i, arr, stepped, n):
				answer += 1
		return answer


class Solution:

	def goodStones(self, n, arr) -> int:
		visited = [0] * n

		def solve(i):
			nonlocal arr, visited, n
			if i < 0 or i >= n:
				return True
			if visited[i] > 0:
				return visited[i] == 2
			visited[i] = 1
			if solve(i + arr[i]):
				visited[i] = 2
				return True
			return False
		return sum((solve(i) for i in range(n)))


class Solution:

	def goodStones(self, n, arr) -> int:
		visited = [False] * n
		bad_stones = set()
		for i in range(n):
			if visited[i]:
				continue
			current_stones = set()
			j = i
			while -1 < j < n:
				if j in bad_stones or j in current_stones:
					bad_stones.update(current_stones)
					break
				if visited[j]:
					break
				current_stones.add(j)
				visited[j] = True
				j += arr[j]
		return n - len(bad_stones)


class Solution:

	def goodStones(self, n, arr) -> int:
		repeat = [0] * n
		bads = 0
		for i in range(n):
			if repeat[i]:
				continue
			x = i
			inds = set()
			ind = 0
			good = True
			while x > -1 and x < n:
				if repeat[x]:
					if repeat[x] == 1:
						break
					bads += ind
					good = False
					break
				repeat[x] = -1
				inds.add(x)
				ind += 1
				x += arr[x]
			if good:
				for i in inds:
					repeat[i] = 1
		return n - bads


class Solution:

	def goodStones(self, n, arr) -> int:
		good = set()
		seen = set()
		for i in range(n):
			if i in good:
				good.add(i)
			elif i not in seen:
				j = i
				curr_set = set()
				while 0 <= j < n and j not in seen:
					seen.add(j)
					curr_set.add(j)
					j += arr[j]
				if j < 0 or j >= n or j in good:
					good.update(curr_set)
		return len(good)


class Solution:

	def solve(self, i, n, arr, ans):
		if i >= n or i < 0:
			return 1
		if ans[i] != -1:
			return ans[i]
		ans[i] = 0
		ans[i] = self.solve(i + arr[i], n, arr, ans)
		return ans[i]

	def goodStones(self, n, arr) -> int:
		ans = [-1] * n
		for j in range(n):
			self.solve(j, n, arr, ans)
		return sum(ans)


class Solution:

	def goodStones(self, n, arr) -> int:
		db = [-1] * len(arr)
		result = 0
		for i in range(0, len(arr)):
			result += self.is_good_stone(i, arr, db)
		return result

	def is_good_stone(self, i, arr, db) -> int:
		if db[i] >= 0:
			return db[i]
		if db[i] == -2:
			db[i] = 0
		else:
			db[i] = -2
			if arr[i] + i >= len(arr) or arr[i] + i < 0:
				db[i] = 1
			else:
				db[i] = self.is_good_stone(arr[i] + i, arr, db)
		return db[i]


class Solution:

	def goodStones(self, n, arr) -> int:

		def good(arr, n, dp, i, ans, vis):
			if i >= n or i < 0:
				return True
			if dp[i] == True:
				return True
			if dp[i] == 2000:
				return False
			if i in vis:
				dp[i] = 2000
				return False
			vis.add(i)
			if good(arr, n, dp, i + arr[i], ans, vis):
				ans[0] += 1
				dp[i] = True
				return True
			else:
				dp[i] = 2000
				return False
		dp = [False for i in range(n)]
		vis = set()
		ans = [0]
		for i in range(n):
			if i in vis:
				continue
			vis.add(i)
			if good(arr, n, dp, i + arr[i], ans, vis):
				ans[0] += 1
				dp[i] = True
			else:
				dp[i] = 2000
		return ans[0]


class Solution:

	def goodStones(self, n, arr) -> int:
		G = [[] for i in range(n)]
		p = []
		for i in range(n):
			ni = i + arr[i]
			if ni >= 0 and ni < n:
				if ni != i:
					G[ni].append(i)
			else:
				p.append(i)
		used = [False for i in range(n)]

		def dfs(s):
			used[s] = True
			c = 1
			for v in G[s]:
				if not used[v]:
					c += dfs(v)
			return c
		c = 0
		for i in p:
			if not used[i]:
				c += dfs(i)
		return c


class Solution:

	def visit(self, i, n, arr, visited):
		if i >= n or i < 0:
			return 2
		if visited[i] == 1:
			return 1
		visited[i] = 1
		visited[i] = self.visit(i + arr[i], n, arr, visited)
		return visited[i]

	def goodStones(self, n, arr) -> int:
		count = 0
		visited = [0 for i in range(n)]
		for i in range(n):
			if visited[i] == 0:
				visited[i] = self.visit(i, n, arr, visited)
		for i in range(n):
			if visited[i] == 2:
				count += 1
		return count


class Solution:

	def goodStones(self, n, arr) -> int:
		res = 0
		visited = [0 for _ in range(n)]
		for i in range(n):
			if visited[i] != 0:
				continue
			pos = i
			good = False
			while visited[pos] != 1:
				visited[pos] = 1
				pos += arr[pos]
				if pos < 0 or pos >= n or visited[pos] == 2:
					good = True
					break
			if good:
				temp = i
				while temp >= 0 and temp < n:
					visited[temp] = 2
					temp += arr[temp]
		for ele in visited:
			if ele == 2:
				res += 1
		return res


class Solution:

	def goodStones(self, n, arr) -> int:
		dp = [-1] * len(arr)
		i = 0

		def good(i, dp, arr):
			if i < 0 or i > n - 1:
				return 1
			if dp[i] != -1:
				return dp[i]
			dp[i] = 0
			dp[i] = good(i + arr[i], dp, arr)
			return dp[i]
		for i in range(len(dp)):
			if dp[i] == -1:
				dp[i] = good(i, dp, arr)
		return dp.count(1)


class Solution:

	def goodStones(self, n, arr) -> int:

		def f(ci):
			if ci < 0 or ci >= n:
				return True
			if dp[ci] != -1:
				return dp[ci]
			if vis[ci] == 1:
				if dp[ci] == -1:
					dp[ci] = False
					return False
				else:
					return dp[ci]
			vis[ci] = 1
			result = f(ci + arr[ci])
			dp[ci] = result
			return result
		ans = 0
		dp = [-1 for i in range(n)]
		vis = [0 for i in range(n)]
		for i in range(n):
			if f(i):
				ans += 1
		return ans


class Solution:

	def goodStones(self, n, arr) -> int:

		def check(i, n, arr, vis):
			if i >= n or i < 0:
				return 1
			if vis[i] != -1:
				return vis[i]
			vis[i] = 0
			vis[i] = check(i + arr[i], n, arr, vis)
			return vis[i]
		temp = [-1] * n
		for i in range(n):
			temp[i] = check(i, n, arr, temp)
		return sum(temp)


class Solution:

	def goodStones(self, n, arr) -> int:
		good_stones = [0] * n
		bad_stones = [0] * n
		for start_stone in range(n):
			if good_stones[start_stone] == 1 or bad_stones[start_stone] == 1:
				continue
			stone = start_stone
			current_path = set()
			current_path.add(stone)
			while True:
				stone = arr[stone] + stone
				if stone < 0 or stone >= n or good_stones[stone] == 1:
					for good_stone in current_path:
						good_stones[good_stone] = 1
					break
				elif bad_stones[stone] == 1 or stone in current_path:
					for bad_stone in current_path:
						bad_stones[bad_stone] = 1
					break
				current_path.add(stone)
		return sum(good_stones)


class Solution:

	def goodStones(self, n, arr) -> int:
		good = set()
		bad = set()

		def dfs(a):
			if a > n - 1 or a in good or a < 0:
				return True
			if a in bad:
				return False
			if a in vis:
				return False
			vis.add(a)
			return dfs(a + arr[a])
		for i in range(n):
			if i in bad:
				continue
			if i in good:
				continue
			vis = set()
			if dfs(i):
				good |= vis
			else:
				bad |= vis
		return len(good)


class Solution:

	def goodStones(self, n, arr) -> int:
		sum = 0
		a = [-1] * len(arr)

		def recursive(i, arr):
			if i > n - 1 or i < 0:
				return 1
			elif a[i] != -1:
				return a[i]
			a[i] = 0
			a[i] = recursive(i + arr[i], arr)
			return a[i]
		for i in range(len(arr)):
			if a[i] == -1:
				a[i] = recursive(i, arr)
		for i in range(len(arr)):
			sum += a[i]
		return sum


class Solution:

	def solve(self, idx, n, arr, dp):
		if idx >= n or idx < 0:
			return 1
		if dp[idx] != -1:
			return dp[idx]
		dp[idx] = 0
		dp[idx] = self.solve(idx + arr[idx], n, arr, dp)
		return dp[idx]

	def goodStones(self, n, arr) -> int:
		dp = [-1] * n
		for i in range(n):
			self.solve(i, n, arr, dp)
		return sum(dp)


class Solution:
	dp = []

	def goodStones(self, n, arr) -> int:
		Solution.dp = [0] * n
		for i in range(n):
			if Solution.dp[i] == 0:
				Solution.dp[i] = Solution.solve(arr, n, i)
		ans = 0
		for x in Solution.dp:
			if x == 2:
				ans += 1
		return ans

	def solve(arr, n, n_i):
		if n_i < 0 or n_i >= n:
			return 2
		if Solution.dp[n_i] == 1 or Solution.dp[n_i] == 2:
			return Solution.dp[n_i]
		Solution.dp[n_i] = 1
		Solution.dp[n_i] = Solution.solve(arr, n, n_i + arr[n_i])
		return Solution.dp[n_i]


class Solution:

	def goodStones(self, n, arr) -> int:
		completed = {}

		def dfs(i, arr, vis, completed):
			if i < 0 or i > len(arr) - 1:
				return True
			if i in completed:
				return completed[i]
			if i in vis:
				return False
			vis[i] = 1
			ans = dfs(i + arr[i], arr, vis, completed)
			completed[i] = ans
			return ans
		for i in range(len(arr)):
			if i not in completed:
				dfs(i, arr, {}, completed)
		ans = 0
		for i in completed:
			ans += completed[i]
		return ans


class Solution:

	def goodStones(self, n, arr) -> int:
		parent = [None] * n
		goodParent = set()
		ans = 0
		for i in range(n):
			if parent[i] is None:
				temp = i
				hops = 0
				while temp >= 0 and temp < n and (parent[temp] is None):
					parent[temp] = i
					temp += arr[temp]
					hops += 1
				if temp not in range(n):
					goodParent.add(i)
					ans += hops
				elif parent[temp] is not None:
					if parent[temp] in goodParent:
						ans += hops
						goodParent.add(i)
		return ans


class Solution:

	def __init__(self):
		self.ans = 0

	def dfs(self, arr, start, vis, loops):
		if start < 0 or start >= len(arr):
			return True
		if vis[start] == True and loops[start] == False:
			return False
		if vis[start] == True and loops[start] == True:
			return True
		vis[start] = True
		if self.dfs(arr, start + arr[start], vis, loops):
			self.ans += 1
			loops[start] = True
			return True
		return False

	def goodStones(self, n, arr) -> int:
		loops = [False for i in range(n)]
		vis = [False for i in range(n)]
		for i in range(n):
			if vis[i] == False:
				self.dfs(arr, i, vis, loops)
		return self.ans


class Solution:

	def dfs(self, ind, arr, dp):
		if ind < 0 or ind >= len(arr):
			return 1
		if dp[ind] != -1:
			return dp[ind]
		dp[ind] = 0
		dp[ind] = self.dfs(ind + arr[ind], arr, dp)
		return dp[ind]

	def goodStones(self, n, arr):
		dp = [-1 for i in range(n)]
		for i in range(n):
			self.dfs(i, arr, dp)
		return sum(dp)


class Solution:

	def solve(self, idx, n, arr, visited):
		if idx < 0 or idx >= n:
			return 1
		elif visited[idx] != -1:
			return visited[idx]
		else:
			visited[idx] = 0
			visited[idx] = self.solve(idx + arr[idx], n, arr, visited)
			return visited[idx]

	def goodStones(self, n, arr):
		visited = [-1 for i in range(n)]
		for idx in range(n):
			self.solve(idx, n, arr, visited)
		return sum(visited)


class Solution:

	def goodStones(self, n, arr) -> int:
		buenos = 0
		visitadas = set()
		buenos = set()
		for i in range(n):
			jumps = []
			jumps.append(i)
			salto = arr[i] + i
			end = False
			while end == False:
				if salto in jumps or (salto in visitadas and salto not in buenos):
					end = True
					visitadas.update(jumps)
				elif salto >= len(arr) or salto < 0 or salto in visitadas:
					end = True
					visitadas.update(jumps)
					buenos.update(jumps)
				else:
					jumps.append(salto)
					salto = salto + arr[salto]
				if len(visitadas) == n:
					i = n
		return len(buenos)


class Solution:

	def goodStones(self, n, arr) -> int:
		phase = [0 for x in range(n)]
		cnt = 0
		for i in range(n):
			if phase[i] == 0:
				self.dfs(i, n, arr, phase)
			if phase[i] == 2:
				cnt += 1
		return cnt

	def dfs(self, i, n, arr, phase):
		if i < 0 or i >= n or phase[i] == 2:
			return True
		if phase[i] == 1:
			return False
		phase[i] = 1
		cc = self.dfs(i + arr[i], n, arr, phase)
		if cc:
			phase[i] = 2
		return cc


from collections import deque

class Solution:

	def goodStones(self, n, arr) -> int:
		c = deque()
		d = {}
		count = 0
		for i in range(n):
			nct = i + arr[i]
			if nct < 0 or nct >= n:
				c.append(i)
			else:
				if nct not in d:
					d[nct] = []
				d[nct].append(i)
		while c:
			idx = c.popleft()
			count += 1
			for nxt in d.get(idx, []):
				c.append(nxt)
		return count


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, arr, visited, n, i):
		if visited[i]:
			return visited[i] == 2
		visited[i] = 1
		j = i + arr[i]
		if 0 <= j < n and (not self.dfs(arr, visited, n, j)):
			return False
		visited[i] = 2
		return True

	def goodStones(self, n, arr) -> int:
		visited = [0] * n
		return sum([self.dfs(arr, visited, n, i) for i in range(n)])


class Solution:

	def dfs(self, i, j, arr, dp):
		dp[i] = 0
		next = arr[i] + i
		if next < 0 or next >= n:
			dp[i] = 1
		elif dp[next] >= 0:
			dp[i] = dp[next]
		else:
			dp[i] = self.dfs(next, n, arr, dp)
		return dp[i]

	def goodStones(self, n, arr) -> int:
		dp = [-1 for i in range(n)]
		count = 0
		for i in range(n):
			self.dfs(i, n, arr, dp)
		for v in dp:
			if v > 0:
				count += 1
		return count


class Solution:

	def goodStones(self, n, arr) -> int:
		unvisited = set(range(n))
		temp = []
		safe = set()
		flag = 0
		while len(unvisited) != 0:
			i = unvisited.pop()
			temp.append(i)
			while True:
				i = i + arr[i]
				if i < 0 or i > n - 1 or i in safe:
					flag = 1
					break
				elif i in unvisited:
					temp.append(i)
					unvisited.remove(i)
				else:
					flag = 2
					break
			if flag == 1:
				for i in temp:
					safe.add(i)
			temp.clear()
			flag = 0
		return len(safe)


class Solution:

	def __init__(self):
		self.ans = 0

	def dfs(self, arr, vis, loop, n, i):
		if i < 0 or i >= n:
			return True
		if vis[i] == True and loop[i] == False:
			return False
		if vis[i] == True and loop[i] == True:
			return True
		vis[i] = True
		if self.dfs(arr, vis, loop, n, arr[i] + i):
			self.ans += 1
			loop[i] = True
			return True
		return False

	def goodStones(self, n, arr) -> int:
		vis = [False for _ in range(n)]
		loop = [False for _ in range(n)]
		self.ans = 0
		for i in range(n):
			if vis[i] == False:
				self.dfs(arr, vis, loop, n, i)
		return self.ans


class Solution:

	def step(self, c, arr, n, visited):
		if c >= n or c < 0:
			return 1
		if visited[c] != -1:
			return visited[c]
		visited[c] = 0
		visited[c] = self.step(c + arr[c], arr, n, visited)
		return visited[c]

	def goodStones(self, n, arr) -> int:
		good = 0
		visited = [-1] * n
		for i in range(n):
			if visited[i] == -1:
				self.step(i, arr, n, visited)
		for i in range(n):
			if visited[i] == 1:
				good += 1
		return good


class Solution:

	def goodStones(self, n, arr) -> int:

		def recur(ind: int) -> int:
			nonlocal goods, visited
			if ind < 0 or ind >= n:
				return True
			if goods[ind] is not None:
				return goods[ind]
			if visited[ind]:
				return False
			visited[ind] = True
			goods[ind] = recur(ind + arr[ind])
			return goods[ind]
		goods = [None] * n
		visited = [False] * n
		for i in range(n):
			if not visited[i]:
				recur(i)
		count = 0
		for i in range(n):
			if goods[i]:
				count += 1
		return count


class Solution:

	def dfs(self, ind, arr, n, phase):
		if ind < 0 or ind >= n or phase[ind] == 2:
			return True
		if phase[ind] == 1:
			return False
		phase[ind] = 1
		ret = self.dfs(ind + arr[ind], arr, n, phase)
		if ret == True:
			phase[ind] = 2
		return ret

	def goodStones(self, n, arr) -> int:
		phase = [0] * n
		count = 0
		for i in range(n):
			if phase[i] == 0:
				self.dfs(i, arr, n, phase)
			if phase[i] == 2:
				count += 1
		return count


class Solution:

	def goodStones(self, n, arr) -> int:

		def fun(arr, i):
			if len(arr) <= i or i < 0:
				return 2
			if dp[i] == 1 or dp[i] == 2:
				return dp[i]
			dp[i] = 1
			dp[i] = fun(arr, arr[i] + i)
			return dp[i]
		dp = [0] * n
		for i in range(n):
			if dp[i] == 0:
				dp[i] = fun(arr, i)
		res = 0
		for i in dp:
			if i == 2:
				res += 1
		return res


class Solution:

	def goodStones(self, n, arr) -> int:
		mp = {}
		dp = [0 for i in range(n)]
		cnt = 0
		ans = 0
		vis = 1
		for i in range(n):
			if dp[i] == 0:
				j = i
				while j < n and j > -1 and (dp[j] == 0):
					dp[j] = vis
					j = j + arr[j]
					cnt = cnt + 1
				if j < n and j > -1:
					if dp[j] not in mp:
						vis += 1
						cnt = 0
					else:
						mp[vis] = 1
						vis = vis + 1
						ans = ans + cnt
						cnt = 0
				else:
					mp[vis] = 1
					vis = vis + 1
					ans = ans + cnt
					cnt = 0
		return ans


class Solution:

	def goodStones(self, n, arr) -> int:
		vis = [0] * n

		def dfsa(ij):
			(arr, vis, n)
			if ij < 0 or ij >= n:
				return True
			if vis[ij] > 0:
				return vis[ij] == 2
			vis[ij] = 1
			if dfsa(ij + arr[ij]):
				vis[ij] = 2
				return True
			return False
		return sum((dfsa(j) for j in range(0, n)))


class Solution:

	def explorePath(self, start, stone_status, n, arr):
		idx = start
		path = []
		while idx < n and idx >= 0 and (stone_status[idx] == 0):
			path.append(idx)
			stone_status[idx] = 2
			idx += arr[idx]
		value = -1
		if idx >= n or idx < 0:
			value = 1
		else:
			value = 1 if stone_status[idx] == 1 else -1
		for idx in path:
			stone_status[idx] = value

	def goodStones(self, n, arr) -> int:
		stone_status = [0] * n
		for idx in range(n):
			if stone_status[idx] == 0:
				self.explorePath(idx, stone_status, n, arr)
		return stone_status.count(1)


class Solution:

	def goodStones(self, n, arr) -> int:
		visit = [0] * n

		def dfss(k):
			(arr, visit, n)
			if k < 0 or k >= n:
				return True
			if visit[k] > 0:
				return visit[k] == 2
			visit[k] = 1
			if dfss(k + arr[k]):
				visit[k] = 2
				return True
			return False
		return sum((dfss(i) for i in range(n)))


class Solution:

	def goodStones(self, n, arr) -> int:
		count = 0

		def check(ind):
			if ind < 0 or ind >= n:
				return -1
			elif vis[ind] != 0:
				return vis[ind]
			vis[ind] = 1
			vis[ind] = check(ind + arr[ind])
			return vis[ind]
		vis = [0] * n
		for i in range(n):
			if vis[i] == 0:
				check(i)
		for i in vis:
			if i == -1:
				count += 1
		return count
		for i in range(n):
			ind = i
			temp = {}
			while ind >= 0 and ind < n:
				if good_bad[ind] == 1:
					for i in temp:
						good_bad[i] = 1
						count += 1
					temp = {}
					break
				elif good_bad[i] == -1 or ind in temp:
					for i in temp:
						good_bad[i] = -1
					temp = {}
					break
				else:
					temp[ind] = 0
					ind += arr[ind]
			for i in temp:
				good_bad[i] = 1
				count += 1
		return count


class Solution:

	def goodStones(self, n, arr) -> int:

		def solve(arr, n, i):
			if i < 0 or i > n - 1:
				return 2
			if dp[i] == 1 or dp[i] == 2:
				return dp[i]
			dp[i] = 1
			dp[i] = solve(arr, n, i + arr[i])
			return dp[i]
		dp = [0] * n
		for i in range(n):
			if dp[i] == 0:
				dp[i] = solve(arr, n, i)
		count = 0
		for i in range(n):
			if dp[i] == 2:
				count += 1
		return count


class Solution:

	def goodStones(self, n, arr) -> int:
		new_arr = [-1 for _ in range(n)]
		cycle = []
		for i in range(n):
			if new_arr[i]:
				while True:
					cycle.append(i)
					i += arr[i]
					if i >= n or i < 0 or new_arr[i] == 1:
						for i in cycle:
							new_arr[i] = 1
						cycle.clear()
						break
					elif new_arr[i] == 0 or i in cycle:
						for i in cycle:
							new_arr[i] = 0
						cycle.clear()
						break
		return sum(new_arr)

	def update_cycle(self, new_arr, cycle, exit):
		for i in cycle:
			new_arr[i] = exit
		cycle.clear()


class Solution:

	def goodStones(self, n, arr) -> int:
		d = {}

		def solve(i, visited):
			if i in d:
				return d[i]
			elif i + arr[i] in d:
				d[i] = d[i + arr[i]]
			elif i + arr[i] >= n or i + arr[i] < 0:
				d[i] = True
			elif i in visited or arr[i] == 0:
				d[i] = False
			else:
				visited.add(i)
				d[i] = solve(i + arr[i], visited)
			return d[i]
		for i in range(n):
			if i not in d:
				solve(i, set())
		cnt = 0
		for i in d:
			if d[i]:
				cnt += 1
		return cnt