CODEWITHSUNDEEP
carrays
Manash Baul
Manash Baul

Reputation: 31

What might be the reason for this kind of difference in output?

I made the follwoing piece of code for a problem.

#include <stdio.h>
#include <stdlib.h>

int main() {
    //code
    int t; int k;
    /*t= length of string and k=character upto which should be counted*/

    int *count = (int*)malloc(26*sizeof(int));
    //Dynamic Array of count.

    scanf("%d %d\n",&t,&k);
    char c;
    for(int i =0;i<t;i++){
       scanf("%c",&c);
       count[c-'A']++;
    }
    int min = 999999;
    for(int i=0;i<k;i++){
        if(min>count[i]) min=count[i]; //Calculating minimum
    }
    if(min==0) printf("0");
    else printf("%d",min*k);
    return 0;
}

Though some of the compilers were giving correct output of the program. The online judge wasn't giving correct output to it. I changed the code a bit and now it works.

#include <stdio.h>
int main() {
    //code
    int t; int k;

    scanf("%d %d\n",&t,&k);
    int count[26];
    char str[100020];

    for(int i=0;i<t;i++) 
        scanf("%c",str+i);
    for(int i =0;i<t;i++){
       count[str[i]-'A']++;
    }

    //Rest from here is unchanged.

    int min = 999999;
    for(int i=0;i<k;i++){
        if(min>count[i]) min=count[i]; //Finding the minimum of count.
    }

    if(min==0) printf("0");
    else printf("%d",min*k);

    return 0;
}

Though both of them is supposed to do the same thing why is the output different by the online judge?

INPUT : 9 3

ACAABCCAB

Correct Output : 6. Wrong output by my code was 9.

P.S Do comment if problem statement is required.

Upvotes: 1

Views: 94

Answers (3)

Peter
Peter

Reputation: 36597

There are a few actual or potential problems, depending on what the online judge does and what compiler (or compiler settings) it uses.

Both cases have undefined behaviour, since elements of count are not initialised. Accessing their values (e.g. which is necessary to increment them) gives undefined behaviour. Among other things, that means the behaviour can vary for creating the arrays in different ways (e.g. malloc() versus an automatic array) in both samples.

The first sample does not check that malloc() succeeds. If malloc() fails (returns NULL) subsequent code that uses count has undefined behaviour.

scanf() can encounter errors. This will be indicated by its return value. For example, it can return EOF to indicate end of stream, or a value indicating the number of values it successfully read. For example, if scanf("%d %d\n",&t,&k) return 1, only the value of t will be changed, and k may not. If k is unchanged, using it (since it is uninitialised) gives undefined behaviour.

Incidentally, scanf("%d %d\n",&t,&k) can have some unexpected effects due to behaviour of the \n on some input. There are plenty of questions here providing examples of problems, and explanations. In short: remove the `\n'.

The first sample has a statement count[c-'A']++ and the second replaces it with count[str[i]-'A']++. Apart from the concern with count being unitialised, this assumes c - 'A' is a valid index. There are two circumstances it will not be, so the operation will increment a value outside count.

  • Input other than an uppercase letter causes c - 'A' to have a value outside the range 0 to 25.
  • [Obscure, but permitted by the standard, and there are character sets with this characteristic]. The set of uppercase letters is not guaranteed to be contiguous, so 'Z' - 'A' may be a value other than 25.

In both cases above, you need to more rigorously check the input for validity.

int min = 999999 has two potential problems. With a compiler that only supports a 16-bit int type, the initialiser overflows, and may give a value different than you expect. If the compiler supports a large enough int (e.g. 32 bit or better) then your program will not correctly handle input values more than 999999. If all input values exceed that value, the calculated value of min will be incorrect.

Upvotes: 0

Clifford
Clifford

Reputation: 93456

Both versions increment count elements without count being initialised. The fact that one works and the other does not is more by luck than judgement. It is a shame that the "judge" does not apply static analysis to the code and just reject it for poor quality rather then simply accepting anything that happens to produce an apparently correct result.

In the second:

int count[26] = {0} ;

In the first:

int* count = calloc(26, sizeof(int) ) ;

but dynamic memory allocation serves no purpose here, and failing to release it is and additional quality issue.

The use of str in the second also serves no purpose. A better solution will be a combination of both - the initialised array, and the use of a single char to receive input.

Upvotes: 0

Barmar
Barmar

Reputation: 780714

Both versions are wrong, because you never initialize the values in count to 0.

In the first version, where you use dynamic allocation, you can use calloc() instead of malloc(), as it automatically zeroes the memory:

int *count = calloc(26, sizeof(*count));

In the second version, where you just declare an array, you can provide an initialization list:

int count[26] = {0};

There's no need for the str array that you put in your second version. Since you're processing the input one character at a time, a single char variable is fine.

There's also no need for the if statement at the end. If min == 0, then k * min is also 0, so printing min * k will print 0.

Upvotes: 2

Related Questions