Counting sort run error

#1


Please point in code why this is showing run error. Every time I do a counting sort problem i get a run error ! how to optimise this?

#2

hey @ankush.bhardwaj0, constraints are high in the question, please make int to long long int. Also you are doing this question in O(n^2).
I have made changes to your code, you can check them here https://ide.codingblocks.com/s/105435

#3

@Gaurav13998 the code is giving wrong answer. We cant use i++ in the else statement, because the loop will iterate by 2. I tried removing that i++ and doing nothing in the else statement. The sample testcase passed but the compiler still showed wrong answer.

#4

hey @ankush.bhardwaj0 sorry I thought it as while loop, Just remove i++ from initialization part of for loop.
But still it will give you TLE, so make >= instead of > in line no 16 of above code.

#5

@Gaurav13998 i made the changes. But still its giving TLE

#6

hey @ankush.bhardwaj0, have you made this change also
so make >= instead of > in line no 16 of above code.

#7

@Gaurav13998 I did that too, but still showed TLE

#8

hey @ankush.bhardwaj0, share me your updated code then.

#9

@Gaurav13998 https://ide.codingblocks.com/s/105571

#10

hey @ankush.bhardwaj0, freq array can contain garbage, so initialised it to 0.
long long int freq[1000000]={0};
Updated code https://ide.codingblocks.com/s/105577

#11

@Gaurav13998 thanks, it worked. But why did it show time limit error. It could’ve shown wrong answer right?

#12

hey @ankush.bhardwaj0, it is giving TLE because freq[i] can have very high garbage value, and that value will keep decrement untill freq[i] becomes 0.