It might just be my wrong implementation of your idea but quicksort is not the best sorting method in this case. The input must be taken space by space so the set up for insertion sort is already in place. This is ofcourse taking into consideration that at max only 5000 numbers are to be sorted.
Insertion Sort (Time ~ 0.29s)
#include <stdio.h>
int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
int N;
scanf("%d", &N);
long A[N];
for(int i = 0; i < N; ++i) /* insertion sort */
{
scanf("%li", &A[i]);
int j = i - 1;
long key = A[i];
while(j >= 0 && A[j] > key)
{
A[j + 1] = A[j];
--j;
}
A[j + 1] = key;
}
long minima = A[1] - A[0];
for(int i = 2; i < N; ++i)
{
minima = A[i] - A[i - 1] < minima ? A[i] - A[i - 1] : minima;
}
printf("%li\n", minima);
}
return 0;
}
Quicksort (Time ~ 0.53s)
#include <stdio.h>
void swap(long* a, long* b)
{
long t = *a;
*a = *b;
*b = t;
}
int partition (long arr[], int low, int high)
{
long pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++)
{
if (arr[j] <= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(long arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main(void)
{
int T;
scanf("%d", &T);
while(T--)
{
int N;
scanf("%d", &N);
long A[N];
for(int i = 0; i < N; ++i) /* insertion sort */
{
scanf("%li", &A[i]);
}
quickSort(A, 0, N - 1);
long minima = A[1] - A[0];
for(int i = 2; i < N; ++i)
{
minima = A[i] - A[i - 1] < minima ? A[i] - A[i - 1] : minima;
}
printf("%li\n", minima);
}
return 0;
}
People have done it in ~0s time like this but I have no clue how that works.
Look, you assigned all the elements of array a value of “0” at start.
When I entered the sample test case
1
5
4 9 1 32 13
You know what I got?
Output - 0
Problem is that you lets say, I input 3 numbers, 1,8,5. The minimum difference is of course, 3,(8-5) but in your code, after these 3 elements, the rest of the elements are assigned a value of 0. And since 0-0 is 0. And 0 <3 , so output is 0.
Now you will say, “I ran the loop only till n elements so how did 0 came in the picture?”
That’s cause honey, you SORTED THE ARRAY TOO!!
Meaning, during sort, the 1,8,5 are pushed as the last 3 digits (4999, 5000 and 4998th indexes) and all indexes from start to end are 0. Your array looks like this after sorting-
{0,0,0,0,0…1,5,8}
I suggest either iterate from back or add some condition like (a[I] != 0 && a[I-1]!=0) to fix it.
Any clue as to why this is WA? Example test case gives the right answer and AFAIK it must give correct answer for any case. Help appreciated.I know I can just use sorting, just wanted to know why was this wrong.
Can’t this problem be solved by finding minimum and second minimum number and printing thier difference and if
repition of number is there printing zero?
dif = []
for i in range(int(input())):
n = int(input())
l = list(map(int,input().split()))
l= sorted(l)
for k in range(n-1):
dif.append(abs(l[k+1]-l[k]))
print(min(dif))
enter code here #include <stdio.h>
int main(void) {
int testcase, length, k = 0;
scanf("%d", &testcase);
while (k != testcase) {
scanf("%d", &length);
int number[100];
for (int m = 0; m < length; m++)
scanf("%d", &number[m]);
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
if (number[i] > number[j]) {
int a = number[i];
number[i] = number[j];
number[j] = a;
}
}
}
int diff = number[1] - number[0];
printf("%d\n", diff);
k++;
}
return 0;
}
I did exactly what it says here yet I am getting wrong answer.
My solution can be found at CodeChef: Practical coding for everyone
Please tell me what’s wrong in my solution.
Even the setters solution is giving time limit exceeded and testers solution is giving run time error SIGABRT . But on submission it accepts answer as 100% correct.What is this nonsense? I wasted my entire day on this.
When you will submit your solution with this approach, it will show time limit exceeded. But when you will submit it, it will be ACCEPTED. Don’t know what the problem is. Maybe different server speed or what else?
#include
using namespace std;
void sort(int p,int n);
int min(int p,int n);
int m=100000010;
int main()
{
int t,i;
//cout<<“Enter the value of t:”;
cin>>t;
while(t)
{
int n;
//cout<<“Enter the value of n:”;
cin>>n;
int a[n],p=a;
for(i=0;i<n;i++)
{
//cout<<“Enter value at index “<<i<<”:”;
cin>>a[i];
}
sort(p,n);
cout<<min(p,n);
t–;
}
}
void sort(int p,int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if((p+j)<(p+j+1))
{
temp=(p+j); (p+j)=(p+j+1); (p+j+1)=temp;
}
}
}
}
int min(int p,int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(((p+j)-(p+j+1))<m)
{
m=((p+j)-*(p+j+1));
}
}
}
return m;
}