Counting Excellent stones in a river with sure and detrimental steps

Geek is in a geekland which has a river and a few stones in it. To start with, a geek can step on any stone. Every stone has a bunch on it representing the worth of the precise step the geek can transfer. If the quantity is +ve then geeks can transfer proper and if the quantity is -ve then geeks can transfer left. Unhealthy Stones are outlined as stones that if geeks steps, will succeed in a unending loop while just right stones are stones which can be secure from unending loops. Go back the selection of just right stones within the river.

Examples:

Enter: [2, 3, -1, 2, -2, 4, 1]
Output: 3
Clarification: Index 3, 5 and six are secure simplest. As index 1, 4, 2 bureaucracy a cycle and from index 0 you’ll move to index 2 which is a part of cycle.

Illustration for example-1

Enter: [1, 0, -3, 0, -5, 0]
Output: 2
Clarification: Index 2 and four are secure simplest. As index 0, 1, 3, 5 shape cycle.

Illustration of example-2

Instinct: The instinct/concept is as follows:

The instinct of this means is that we commence from any stone provide within the given array and we can make recursive name for different stones, to start with we think that the stones which seems within the recursive name are unhealthy stone but when we will be able to succeed in on the remaining index of the array then we go back the recursive name to the stone from the place we commence our adventure for every recursive name and we can mark them as just right stones different sensible they stays unhealthy stone.

Means: To resolve the issue practice the underneath concept:

The issue can also be solved the usage of Dynamic Programming. The speculation here’s to care for a visited array or listing of measurement equivalent to the scale of the given array  which is initialized via -1. If the worth of visited array at any index, i is -1 that suggests we have now now not visited the stone provide on the index, i within the given array. Every time we commence our adventure from any index of the given array we mark the worth of visited array on the similar index as 0 price and we do it recursively for every index of the given array. If we succeed in out of the array via following some trail than the indexes that looks on this trail we mark them as just right indexes and worth the visited array at the ones indexes can be 1 because of this “We discuss with the ones indexes to succeed in out of the array and the stones which might be provide on the ones indexes are mentioned to be just right stones”, another way price of the visited array at the ones indexes stays 0.

Beneath are the stairs for the above means:

• Claim a visited array, vis of measurement equivalent to the scale of enter array/vector globally in order that it may be accessed in any serve as.
• Initialize the visited array, vis via -1 which denotes that the stones aren’t visited.
• Iterate the enter vector as we will be able to get started the adventure from any index, for each and every index we can test if is it a just right stone or unhealthy stone the usage of a helper serve as resolve().
• Take a look at if vis[i] == -1, and phone the resolve() serve as that takes two arguments, enter array, and present index of the stone, i.
• Within the helper serve as,
  • test if, i < 0 or i ≥ enter array measurement, that suggests index i has already reached out of the array so, go back 1.
  • test if vis[i] != -1, because of this index i has already been visited, and go back vis[i].
  • If the above two aren’t the case, that suggests the stone at index i isn’t visited prior to now and we’re nonetheless within the enter array. So, mark vis[i] = 0 to turn it is a unhealthy stone.
  • Recursively name resolve() serve as. resolve() serve as returns some integer price both 0 or 1 which can be saved within the visited array, vis[i] = resolve(array, i+array[i]).
  • When the recursive name is finished go back the worth of the visited array, vis at index i, go back vis[i]. 
• Initialize one variable, say, depend via 0 to calculate the selection of just right stones.
• Iterate the visited array and test if the worth of the visited array at any index is 1, vis[i] = 1 because of this a stone on the similar index is a superb stone, increment depend variable via 1.
• Go back the worth of the depend variable.

Beneath is the implementation for the above means:

Time Complexity: O(N), N is the selection of stones
Auxiliary House: O(N)