I have a theory, and it’s an unusually subtle one.
Weirdly, when compiling as C, gcc doesn’t complain about this, but when compiling as C++ it does, very loudly:
[simon@simon-laptop][17:42:07]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling k_purushottam-ENTEXAM.cpp
k_purushottam-ENTEXAM.cpp: In function ‘int main()’:
k_purushottam-ENTEXAM.cpp:33:53: error: invalid conversion from ‘long long int (*)(const void*, const void*)’ to ‘__compar_fn_t {aka int (*)(const void*, const void*)}’ [-fpermissive]
qsort(arr1,n-1,sizeof(long long int),compare);
^
In file included from /usr/include/c++/7/cstdlib:75:0,
from /usr/include/c++/7/stdlib.h:36,
from k_purushottam-ENTEXAM.cpp:4:
/usr/include/stdlib.h:827:13: note: initializing argument 4 of ‘void qsort(void*, size_t, size_t, __compar_fn_t)’
extern void qsort (void *__base, size_t __nmemb, size_t __size,
As the error suggests, compare
should return an int
, not a long long int
. Presumably, internally qsort
treats the result of compare
as an int
, but your compare
is subtracting long long int
s and returning the result, and this might overflow an int
, meaning that qsort
gets the wrong ordering for pairs of elements, completely breaking its attempt at sorting them.
Changing your compare
to something like this:
int compare(const void *p1,const void *p2)
{
const long long int p1AsLong = *(long long int *)p1;
const long long int p2AsLong = *(long long int *)p2;
if (p1AsLong < p2AsLong)
return -1;
if (p1AsLong > p2AsLong)
return +1;
return 0;
}
might work.
Edit:
I tell a lie: compiling it as C does cause gcc to warn about it:
[simon@simon-laptop][17:49:20]
[~/devel/hackerrank/otherpeoples]>gcc k_purushottam-ENTEXAM.c -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv -Wall -Wextra
k_purushottam-ENTEXAM.c: In function ‘main’:
k_purushottam-ENTEXAM.c:46:46: warning: passing argument 4 of ‘qsort’ from incompatible pointer type [-Wincompatible-pointer-types]
qsort(arr1,n-1,sizeof(long long int),compare);
^~~~~~~
In file included from k_purushottam-ENTEXAM.c:4:0:
/usr/include/stdlib.h:827:13: note: expected ‘__compar_fn_t {aka int (*)(const void *, const void *)}’ but argument is of type ‘long long int (*)(const void *, const void *)’
extern void qsort (void *__base, size_t __nmemb, size_t __size,
^~~~~
Edit3:
Here’s a specific test input that your solution fails on.