So, I used a quick sort to implement the problem in Java. It works fine for the given input set but gives wrong answer. Can someone help me please???
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
public class Main {
public static int partition(int arr[], int left, int right){
int pivot=arr[(left+right)/2];
int i=left;
int j=right;
int temp;
while(i<=j){
while(arr[i]<pivot)i++;
while(arr[j]>pivot)j--;
if(i<=j){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
i++;
j--;}}
return i;}
public static void QuickSort(int arr[], int left, int right){
int index=partition(arr,left,right);
if(left<index-1)QuickSort(arr,left,index-1);
if(index<right)QuickSort(arr,index,right);}
public static void main(String[] args) throws IOException {
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintStream ps = new PrintStream(System.out);
StringBuilder sb = new StringBuilder("");
int t=Integer.parseInt(f.readLine());
int [] turbo=new int[t];
for(int i=0;i<t;i++)turbo[i]=Integer.parseInt(f.readLine());
QuickSort(turbo,0,t-1);
for(int i=0;i<t;i++){
if(i==t-1)sb.append(turbo[i]).append("\n");
else{
if(turbo[i]!=turbo[i+1])
sb.append(turbo[i]).append("\n");}}
ps.println(sb);}
}
1 Like
Try the input
4
1
1
2
2
the correct answer is
1
1
2
2
you propably misunderstood non decreasing order, read more on wikipedia.
Two hints to you:
- you don’t need to implement sort in Java, there are Collections.sort() and Arrays.sort() methods
- quick sort in worst case has complexity O(n^2), so someone can challenge your solution in contests where it is possible to challenge (hack) solution.
3 Likes
You Picked the question in the wrong way.
The question is straight forward -You just have to sort the given data-set in ascending order.
But after analyzing your code ,i think you misunderstood that only one copy of the repeated members is to be printed .
No ,that’s not the case .
And here is the proof ,For the test case
10
5
3
5
6
7
1
9
7
3
2
your code was generating the following output
1
2
3
5
6
7
9
Clearly you were avoiding the printing of repeated members.
In order to fix it :
Just comment the three lines in printing steps as shown :
QuickSort(turbo,0,t-1);
for(int i=0;i<t;i++){
//if(i==t-1)sb.append(turbo[i]).append("\n");//No need of it
// else{
//if(turbo[i]!=turbo[i+1])//Wrong Answer due to this
sb.append(turbo[i]).append("\n");
// }
}
ps.println(sb);}
}
4 Likes
@avengee - “print given numbers in non decreasing order.”. u considered it as strictly non decreasing order I guess.
@ritesh_gupta is correct , that’s the only bug ,your quick sort looks absolutely fine .
2 Likes
@ritesh_gupta: Thank you so much for the help. I didn’t submit yet because I have a small question.
So, in non-decreasing order an element can be either equal or greater than the previous element?
My question is with the example input and output set in the problem statement:
Example
Input:
5
5
3
6
7
1
Output:
1
3
5
6
7
This example has avoided repeated numbers. What is it? Or am I still mistaken about the definition of non-descending numbers?
@avengee: first number is not from the sequence, it is the sequence length 
@belista: Thank you for your valuable tips. As I previously stated in the comment for above post, I’m confused with the example. Any help is greatly appreciated:).
I replied in ritesh_gupta’s answer.
Above or below is relative, answers are ordered by decreasing number of up votes and despite of that I answered first and ritesh_gupta copied answer 3 hours later he got more up votes…
@avengee :Read the problem statement once again,especially “Input t – the number of numbers in list, then t lines follow [t <= 10^6].Each line contains one integer: N [0 <= N <= 10^6]”.
So the First line 5 means there are 5 elements in the data set and these 5 elements are 5 3 6 7 1 .So our task is to sort the numbers 5 3 6 7 1
Thanks all:). I’m a new coder and sometimes I get so confused:). Thank you again for taking your valuable time to help me out for this simple question:).
Anyways, thank you again:)
#include <stdio.h>
int v[1000001]={0};
int main()
{
int n,i,a;
scanf("%d",&n);
for (i=0;i<n; i++){ scanf("%d",&a); v[a]++; }
for (n=0;n<=1000000; n++) for (i=0;i<v[n];i++) printf("%dn",n);
return 0;
}
i am getting wrong answer on this code.
please someone help.