5
\$\begingroup\$

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.

\$\endgroup\$
8
  • 4
    \$\begingroup\$ Why is n passed into the function if the first thing you do is set it to zero? \$\endgroup\$ Jan 14 '12 at 18:04
  • 5
    \$\begingroup\$ Goto here will probably get you a failing grade. Did you come from a BASIC or assembler background? ALso, I don't think the above is working as well as you believe. \$\endgroup\$
    – Michael Dorgan
    Jan 14 '12 at 18:05
  • \$\begingroup\$ @JonathanLeffler well actually that part was written by some one else....i just had to write that particular function.If needed i could use the n or just let it be \$\endgroup\$
    – agasthyan
    Jan 14 '12 at 18:06
  • 2
    \$\begingroup\$ Does the string include the braces you showed? Can spaces appear? What should happen if a non-digit, non-comma (non-space) appears? \$\endgroup\$ Jan 14 '12 at 18:11
  • 2
    \$\begingroup\$ Regarding goto: You are going to hear, again and again, that you should never use goto. Like any best practice, try to adhere to it, but take it with a grain of salt. Since C lacks exceptions and closures, and does not guarantee optimized tail recursion, there are legitimate uses for goto (e.g. jumping to cleanup code at the end of your function). However, it takes a lot of maturity to know when goto is a good idea. Take a look at this parser I wrote in C a couple years ago, and decide for yourself if it abuses goto. \$\endgroup\$
    – Joey Adams
    Jan 15 '12 at 1:08
11
\$\begingroup\$

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;
}
\$\endgroup\$
7
\$\begingroup\$

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).

\$\endgroup\$
2
  • \$\begingroup\$ well actually output1 was globally declared hence was skipped from the code..apology for dat..... \$\endgroup\$
    – agasthyan
    Jan 14 '12 at 18:16
  • \$\begingroup\$ Don't use global variables - especially not for a neat, self-contained function like this. They make it harder to use the code; they make it much harder to reuse the code. \$\endgroup\$ Jan 14 '12 at 18:22
5
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

I'm going to focus 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;
}

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This doesn't compile (at least not with GCC). It is a syntax error to declare a variable after a label: int digit = str[i] - '0';. You'll need to wrap that part in braces. \$\endgroup\$
    – Joey Adams
    Jan 16 '12 at 18:40
  • \$\begingroup\$ @JoeyAdams — ah yes, thank you. Fixed in the above. \$\endgroup\$ Jan 16 '12 at 20:01
1
\$\begingroup\$

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Don't take it further than this - it is homework... \$\endgroup\$
    – Michael Dorgan
    Jan 14 '12 at 18:14
  • 1
    \$\begingroup\$ Note: If the character is a }, you still have to post-process the number (calculate the average and update count if appropriate) before returning. \$\endgroup\$ Jan 15 '12 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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