3
\$\begingroup\$

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?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Are you sure your solution is correct? It doesn't seem correct to me at first glance. \$\endgroup\$
    – JS1
    Jul 8, 2016 at 9:18
  • \$\begingroup\$ I'm still waiting for better solution. If anybody know then please answer. \$\endgroup\$
    – codeFreak
    Jul 13, 2016 at 9:52

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ This sets each byte to -1 (0xFF), ints are bigger than a byte. It works because each byte of the two's complement for -1 is 0xFF, but the standard doesn't enforce two's complement for signed types. The pedantic, portable way would be a loop. \$\endgroup\$ Jul 10, 2016 at 21:18
  • \$\begingroup\$ @AndreaBiondo That's a fair point, I'd typically only use memset to initialise to 0, or if I'm setting up a buffer to a particular character. \$\endgroup\$
    – forsvarir
    Jul 10, 2016 at 22:38
3
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.