The Chicken McNuggets problem, presented in last week’s Lesson, shows code that outputs the highest McNuggets number from 1 to 100. This value isn’t a combination of 6, 9, or 20, the number of the pieces offered in the McDonald’s Chicken McNuggets packages.

The C language solution presented on Rosetta Code works, but it uses the detested goto statement to cut through the nested loops. Obviously, nested loops are required to calculate the various permutations of 6, 9, and 20, but there must be some other way to code a solution without using goto statements.

For my approach, I use nested loops but they’re coupled with a 100 element array, nuggets[]. This array is what keeps track of the McNugget numbers. It allows the nested loops to track the numbers by resetting values in the array. When the loops have run through all the permutations, a final loop reviews the array to find the highest non-McNuggets value.

2020_12_05-Lesson.c

#include <stdio.h>

int main()
{
    int x,i,s,n,t,max;
    int nuggets[100];

    /* initialize array */
    for( x=0; x<100; x++ )
        nuggets[x] = 1;

    /* find the McNuggets number */
    i = 0;
    while( i<100 )
    {
        /* loop through sixes first */
        for( s=0; s*6<i; s++ )
        {
            if( s*6 == i )
                nuggets[i] = 0;
            /* nines loop */
            for( n=0; n*9<i; n++ )
            {
                if( s*6 + n*9 == i )
                    nuggets[i] = 0;
                /* twenties loop */
                for( t=0; t*20<i; t++ )
                {
                    if( s*6 + n*9 + t*20 == i )
                        nuggets[i] = 0;
                }
            }
        }
        i++;
    }

    /* find largest value McNuggets number */
    max = 0;
    for( x=0; x<100; x++ )
    {
        if( nuggets[x]==1 )
            max = x;
    }
    printf("Maximum non-McNuggets number is %d\n", max);

    return(0);
}

The nuggets[] array is initialized at in the for loops at Lines 9 and 10. A value of 1 in the array indicates a non-McNuggets number. The rest of the code works to reset elements to 0 when a McNuggets number is found.

Like the example on Rosetta Code, my code uses a master while loop at Line 14 to plow through values 0 through 99. Three nested for loops test the permutations of 6, 9, and 20, hunting for McNugget values. When a value is found, the element represented by while looping value i is reset:

nuggets[i] = 0;

My solution removes the i++; statements from within the for loops and sets it in the master while loop. Yes, this code churns more often than the original solution, but it avoids the dratted goto statements.

A final for loop at Line 39 determines the highest element number that has retained its 1 (non-McNuggets) value. The output is the same as the goto-infested original:

Maximum non-McNuggets number is 43

I modified the code to calculate the highest McNuggets value below 1000. It was still 43, which is the same value the original code returned when I changed its limit as well. This change got me to thinking that 43 may be the highest non-McNuggets number possible.

To test my theory, I changed the looping value to 1,000,000. This change made me notice how long it took the code to run. While the result continues to be 43, the original program and mine had two different runtimes, with the original taking far less time to execute. Though using goto statements may help with the speed, I wouldn’t recommend using them, especially because it isn’t the only option available.