Count the number of ways to obtain a sum, with consecutivity restriction

Question

A cricketer can score 1, 2, 4 or 6 in a ball. Find in how many ways the player can score a total of "n" runs without hitting 3 consecutive boundaries. Note: Scoring 4 or 6 is considered as a boundary.

My solution is:

int *arr; //global array to save calculated ways
int waysUtil(int n, int boundaries){

     if(n==0)
        return 1;
     if(n<1)
        return 0;

    if(arr[n]>0)
        return arr[n];//if already calculated return the value
    int hit_one = waysUtil(n-1, 0);
    if(n-1 >=0) arr[n-1]= hit_one;
    int hit_two = waysUtil(n-2, 0);
    if(n-2 >=0) arr[n-2] = hit_two;
    int hit_four=0, hit_six=0;
    // for 4 and 6 check number of consecutive boundaries hit.
    //if less than two then calculate
    if(boundaries<2 ){

        hit_four = waysUtil(n-4, boundaries + 1);
        if(n-4 >=0) arr[n-4] = hit_four;
        hit_six = waysUtil(n-6, boundaries + 1);
        if(n-6 >=0) arr[n-6] = hit_six;

    }
    return hit_one + hit_two + hit_four + hit_six;
}


int ways(int score){
    arr =(int*)malloc(sizeof(int)*score);
    memset(arr, -1, sizeof(arr));
    int noOfWays = waysUtil(score, 0);
    free(arr);
    return noOfWays;
}

Is better solution possible?

Answer 1

This looks wrong:

memset(arr, -1, sizeof(arr));

This is setting sizeof(int*) bytes of arr to -1. It doesn't set the entire contents of arr.

You should probably be doing this:

int arr_size = sizeof(int)*score;
arr = (int*)malloc(arr_size);
memset(arr, -1, arr_size);

Although as pointed out by @Andrea Biondo, this only works because most architectures and compilers are based around twos complement numbers. There are some exceptions to this rule, which you're likely to know about if they effect you.

Answer 2

Bug #1

In ways(), you allocate an array of length equal to score like this:

arr =(int*)malloc(sizeof(int)*score);

Then you call waysUtil(score, 0). But in waysUtil(), you deference arr[n], where in this case n = score. So you are reading off the end of the array. You need to allocate an array one larger than score to fix this.

Bug #2

You program doesn't return the correct answer. The problem is that your cache arr only holds the answer to "how many ways are there to get to this score without hitting 3 boundaries". But the cache doesn't contain information about "how many boundaries did I hit just before getting to this score". The problem occurs when you get to score 12 or higher. At this point, the cache for score 8 contains one entry for the possibility 4 + 4. But the code will allow the combination 4 + 4 + 4 to be counted when it shouldn't.

I wrote my own program to solve the problem and got the answer 609 for score 12, and your program got the answer 610. All scores above 12 also got differing answers. To fix the problem, your cache should be of the form:

int arr[MAX_SCORE][3];

where each array entry arr[score][b] should hold "how many ways are there to reach score with the previous b entries all being boundaries"? Once you do that, you can correctly rule out the 3-boundaries-in-a-row cases.

Hint: the final solution to how many ways to reach score will be arr[score][0] + arr[score][1] + arr[score][2].

The correct solution

I have written my own solution to the problem using the technique I described in the previous section, but I feel like I should give the OP a chance to fix their program before I just give my solution. I will, however, give some answers from my program so that the OP can verify correctness:

Score =  1, Ways = 1
Score =  2, Ways = 2
Score =  3, Ways = 3
Score =  4, Ways = 6
Score =  5, Ways = 10
Score =  6, Ways = 19
Score =  7, Ways = 33
Score =  8, Ways = 60
Score =  9, Ways = 106
Score = 10, Ways = 191
Score = 11, Ways = 340
Score = 12, Ways = 609
Score = 13, Ways = 1087
Score = 14, Ways = 1942
Score = 15, Ways = 3469
Score = 16, Ways = 6197
Score = 17, Ways = 11072
Score = 18, Ways = 19782
Score = 19, Ways = 35344