Codility - NumberSolitaire

by ne on 2022-09-05 under Algo/DS/Problems tagged with codility

The problem belongs to Codility, here is the link to the problem

Following code segment contains the description in the class comments, followed by fully working solution, then a brief detail about the solution afterwards

``````

/**
* N consecutive squares are given, (0 to N − 1), each has a number written on it. A six sided die is thrown in every turn and can give a number 1 to 6. We start from 0 and
* want to reach to N &minus 1, making a hop of the number given by throwing die in every turn. While going from 0 to N &minus 1 , we keep calculating the sum of numbers.
* Since there can be multiple ways to reach our goal, we need to return the maximal sum possible.
* Example input : { 1, -2, 0, 9, -1, -2}
* if we go with indexes 0, 3 and 5 the sum becomes 8, which is maximal.
*/
public class NumberSolitaire {
// solution using dp
public int solution(int[] A){
int[] dp=new int[A.length+1];
dp[0]=A[0];
dp[1]=A[1]+dp[0];
for(int i=2;i < A.length;i++){
int max=Integer.MIN_VALUE;
for(int j=i-1;j >= i-6 && j>=0;j--){
max = Math.max(dp[j],max);
}
dp[i]=A[i]+max;
}
return dp[A.length-1];
}
// main method to test out
public static void main(String[] args){
System.out.println(new NumberSolitaire().solution(new int[]{1,-2,0,9,-1,-2}));
}
}

```
```

The complexity here is O(6N) which is O(N). The solution is fully acceptable with score of 100% in codility.

Since there are multiple ways to reach the goal and every hop needs information about the sum accumulated so far from the previous jump, it should come to us that it is dynamic programming problem. We can keep a track of the sum so far in a simple dp named array, and from every next possible jump according to the die, we can get the max possible outcome from that and add to the sum that we have. At the end we will have the max sum possible at each index and we can then return the value for last position which is required answer.