CODEWITHSUNDEEP
arraysalgorithmdata-structures
discoverAnkit
discoverAnkit

Reputation: 1151

No. of paths in integer array

There is an integer array, for eg.

{3,1,2,7,5,6}

One can move forward through the array either each element at a time or can jump a few elements based on the value at that index. For e.g., one can go from 3 to 1 or 3 to 7, then one can go from 1 to 2 or 1 to 2(no jumping possible here), then one can go 2 to 7 or 2 to 5, then one can go 7 to 5 only coz index of 7 is 3 and adding 7 to 3 = 10 and there is no tenth element.

I have to only count the number of possible paths to reach the end of the array from start index.

I could only do it recursively and naively which runs in exponential time.

Somebody plz help.

Upvotes: 0

Views: 83

Answers (1)

Terry Storm
Terry Storm

Reputation: 497

My recommendation: use dynamic programming.

If this key word is sufficient and you want the challenge to find a possible solution on your own, dont read any further!

Here a possible DP-algorithm on the example input {3,1,2,7,5,6}. It will be your job to adjust on the general problem.

create array sol length 6 with just zeros in it. the array will hold the number of ways.

sol[5] = 1;
for (i = 4; i>=0;i--) {
     sol[i] = sol[i+1];
     if (i+input[i] < 6 && input[i] != 1)
         sol[i] += sol[i+input[i]];             
}

return sol[0];

runtime O(n)

As for the directed graph solution hinted in the comments :

Each cell in the array represents a node. Make an directed edge from each node to the node accessable. Basically you can then count more easily the number of ways by just looking at the outdegrees on the nodes (since there is no directed cycle) however it is a lot of boiler plate to actual program it.

Adjusting the recursive solution

another solution would be to pruning. This is basically equivalent to the DP-algorithm. The exponentiel time comes from the fact, that you calculate values several times. Eg function is recfunc(index). The initial call recFunc(0) calls recFunc(1) and recFunc(3) and so on. However recFunc(3) is bound to be called somewhen again, which leads to a repeated recursive calculation. To prune this you add a Map to hold all already calculated values. If you make a call recFunc(x) you lookup in the map if x was already calculated. If yes, return the stored value. If not, calculate, store and return it. This way you get a O(n) too.

Upvotes: 2

Related Questions