String traversal program in C

Before addressing efficiency, some improvements I would recommend:

• No need for a goto here. This is easy to turn into a for loop.

• Say const char *input2, to avoid accidentally modifying your input string.

• Use whitespace to clarify order of operations:

  • if(sum > n<<2) Relational operators and shifts are right next to each other on the operator precedence table.

  • sum += *input2 - '0';

• Take out the asterisk in *input2++; You aren't using the character.

And a more subtle issue:

• isdigit expects an unsigned char casted to an int. char is usually signed (but on some platforms, it's unsigned). Thus, if one of your input bytes is not ASCII, it may lead to undefined behavior.

  isdigit((unsigned char) *input2)
  

Here is an editorialized version of your code:

void GetCount(const char* input2)
{
    int sum = 0;    /* Sum of digits in current number */
    int n = 0;      /* Number of digits in current number */

    for (;;)
    {
        input2++;
        if (*input2 == '\0')
            break;

        /*
         * If we have a digit, increment sum and n appropriately.
         *
         * Otherwise (we ran into a brace or comma), tally the current number,
         * and clear the stats for the next number.
         */
        if(isdigit((unsigned char) *input2))
        {
            sum += *input2 - '0';
            n++;
        }
        else
        {
            if(sum > n<<2)
                output1++;
            sum = 0;
            n = 0;
        }
    }
}

Let's look at the sum > n<<2 line, which looks wrong to me. Here's the condition we want to test (simple, but inefficient):

1. (double)sum / n >= 5.0

We can express it in integer arithmetic as:

2. sum >= n * 5

Now I get what you were trying to do. Your next steps converted the multiplication to a less expensive shift:

3. sum > n * 4
4. sum > n<<2

Step 3 is wrong. sum can be greater than n * 4 but less than n * 5. Example:

34566: sum = 24, n = 5

n * 4 = 20      sum >  n * 4 holds
n * 5 = 25      sum >= n * 5 does not hold

The good news is, we can get rid of the multiply and even the shift! Just increment n by 5 each iteration:

        if(isdigit((unsigned char) *input2))
        {
            sum += *input2 - '0';
            n += 5;
        }
        else
        {
            if(sum >= n)
                output1++;
            sum = 0;
            n = 0;
        }

Finally, let's get rid of that isdigit. It's probably pretty fast, but it has to guard against EOF and do a table lookup. Assuming your input is guaranteed to be in the syntax you describe (non-negative integers delimited by commas and wrapped in braces), you can test for two specific characters instead of having to do a character class lookup.

Here is a final version, with more cleanups:

/*
 * Given a list of numbers in the following syntax:
 *
 *     list ::= '{' '}'
              | '{' number (',' number)* '}'
 *
 *     number ::= [0-9]+
 *
 * Count how many numbers have digits that average to 5 or more.
 */
int GetCount(const char* input)
{
    int sum = 0;                /* Sum of digits in current number */
    int length_times_five = 0;  /* Number of digits in current number, times 5 */
    int ret = 0;

    /*
     * Handle empty list.  Otherwise, the following code
     * would return 1 because 0 >= 0.
     */
    if (input[0] == '{' && input[1] == '}')
        return 0;

    while (*++input != '\0')
    {
        if (*input == ',' || *input == '}')
        {
            if(sum >= length_times_five)
                ret++;
            sum = 0;
            length_times_five = 0;
        }
        else
        {
            sum += *input - '0';
            length_times_five += 5;
        }
    }

    return ret;
}

My answer.

It's mostly redundant with the previous (better) answer by @Joey. It got my vote.

It's still got a twist of it's own, so here goes.

It's an annotated revision. It's still O(n) -- don't see how it could NOT be. It's more idiomatic and less redundant. It's not compiled or tested.

It doesn't raise the question "What does (sum>n<<2) have to do with anything?"

It's a non-void return type. It describes the type of the result. It doesn't mess with some global like output1 that you would have to remember to define somewhere.

unsigned int GetCount(char* input2)
{
    unsigned count = 0;
    int sum = 0;

It's a comment. It explains things that aren't at all apparent like, just for example, what (sum>n<<2) might have to do with anything.

    int saw_a_digit = 0; /* only consider counting (again) after seeing a digit */

It's a loop. It's better than a goto. It's a for loop. It works well when incrementing a pointer once after each time through the loop.

It's got a test for null that only needs to be in this one place.

It's got an increment that doesn't need to dereference the pointer with '*'.

    for(; *input2; input2++)
    {
        if(isdigit(*input2))
        {

It's a minor optimization over summing digits. It doesn't require counting digits or calculating an average or calculating anything even remotely like (sum>n<<2). Why would it? It's a little tricky, so there's another comment.

            /* We don't need the digit, just how it relates to 5.
             * Amounts > 5 gets canceled out by amounts < 5,
             * 0s and 9s have more influence than 4s and 6s.
             * '5' has no effect at all.
             * This would take a very long string of digits mostly 
             * on on the same side of 5 to overflow sum. */

It's white space in a non-trivial statement. It's readable.

            sum += *input2-'5';
            saw_a_digit = 1;
        }
        else if (saw_a_digit) // found end of digit string
        {
             if (sum >= 0) // low influence did not dominate
             {
                 ++count;
             }
             sum = 0;
             saw_a_digit = 0;
        }
    }
}

It's an alternative that uses two smaller loops. It avoids mode variables like saw_a_digit. It MAY be a little faster.

unsigned int GetCount(char* input2)
{
    unsigned count=0;
    int sum;
    while (*input2)
    {
        for (;!isdigit(*input2);input2++) /* skip non-digits */
            if (!*input2)
                return count;
        sum=0;
        do {
            /* We don't need the digit, just how it relates to 5.
             * Amounts > 5 get canceled out by amounts < 5,
             * 0s and 9s have more influence than 4s and 6s.
             * '5' has no effect at all.
             * This would take a very long string of digits mostly 
             * on on the same side of 5 to overflow sum. */
            sum += *input2-'5';
        } while (isdigit(*++input2));
        if (sum>=0) // low influence did not dominate
        {
            ++count;
        }
    }
    return count;
}

Your function should return the number of numbers that meet your criterion, and you only need the input string, so the interface should be:

int GetCount(const char *str)

You really don't need the goto statements; you need a while loop. I would probably have a loop like:

while ((c = *str++) != '\0')
{
    ...
}

You haven't shown where output1 is defined or initialized. It should probably be a local variable initialized to 0 and should be the value returned.

Your calculation is dubious. For a number of m digits, the sum of its digits should be greater than or equal to 5 * m.

Also, note that:

*input2++;  

does exactly the same as:

input2++;  

While the compiler will eliminate the dereference (since it doesn't use it), so there won't be a runtime performance, there is no point in fetching a value which you never use. *input++ has its uses, but as the sole expression in a statement, it is not needed. GCC set fussy will warn you about it:

error: value computed is not used [-Werror=unused-value]

(compiled with -Werror to convert all warnings into errors).

Joey Adams and Paul Martel both gave excellent answers. I'm going to throw in a different type of answer --- focusing not on speed, but on clarity with regard to the original specification:

int GetCount(const char *str)
{
    int count = 0;
    int sum_digits = 0;
    int num_digits = 0;

    for (int i = 0; str[i]; i++)
    {
        switch (str[i])
        {
            case '{':
            {
                break;
            }

            case '0': case '1': case '2': case '3': case '4':
            case '5': case '6': case '7': case '8': case '9':
            {
                int digit = str[i] - '0';
                sum_digits += digit;
                num_digits++;
                break;
            }

            case ',':
            case '}':
            {
                if (num_digits > 0)  // Could be 0 if input was "{}",
                    if (sum_digits >= num_digits * 5)  // e.g., sum_digits/num_digits > 5
                        count++;
                sum_digits = num_digits = 0;  // Reset accumulators for next input number.
                break;
            }

            default:
            {
                return -1;  // Invalid input character encountered
            }
        }
    }

    return count;
}

Hmm, but that actually turns out to be extremely fast. With a good compiler, the str[i] should be just as fast as incrementing a pointer. There is still a table lookup here, by the way. It's hidden in the switch statement. But such things are extremely fast.

First, what is the n parameter for, and do you need it? Second, try structuring your code basically like:

function definition
    int n = 0;
    int val = 0;
    int count = 0;
    iterate over the string
        if the character is a numeral
            val += character value
            n++;
        if the character is a ,
            if the avg (which is val / n) is greater than 5
                count++
            reset n and val to zero
        if the character is a }
            return count
        else
            reset n and val to zero
     return count

Or something to that effect