patterncModerate

String traversal program in C

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

homework codereview c stackoverflow optimization strings

programstringtraversal

Problem

My task was to write a function in C where a string such as {2210090,34566,87234,564676} would be given as input and the function had to find out the count of numbers separated by comma whose average of single digits is greater than or equal to 5.

In the below example, the average of 2210090 is 2, the average of 34566 is 4.8, the average of 87234 is 4.8 and the average of 564676 is 5.6, hence the count is 1.

void GetCount(int n,char* input2)
{
    int sum=0;
    n=0;
    h:
    *input2++;  
    if((*input2) && !isdigit(*input2))
    {
        if(sum>n<<2)
            output1++;
        sum=0;
        n=0;
        goto h;
    }
    else if(*input2!='\0')
    {
        sum+=*input2-'0';
        n++;
        goto h;
    }
}

The first parameter n is the total count of number. The program is working fine and I just wanted to know if anyone could give input on improving the time complexity of the program. I would also appreciate a better way of solving this problem, reducing the number of ifs and gotos or completely eliminating the need of if or goto.

Solution

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

-

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

 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;
}

Code Snippets

isdigit((unsigned char) *input2)

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;
        }
    }
}

1. (double)sum / n >= 5.0

2. sum >= n * 5

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

Context

StackExchange Code Review Q#7818, answer score: 11

Revisions (0)

No revisions yet.