Write sorted in ascending order numbers that were drawn more than once. [ C ]

Question

I can't solve this one problem

this code has Time limit exceeded, so i need to make time complexity smoller, i think

  #include <stdio.h> 
  int main() 
  {
    int a[100000], i, j, min, b, tmp;
    scanf("%d", &b); 
    for (i = 0; i < b; i++)
    {
      scanf("%d", &a[i]);
    }

    for (i = 0; i < b; i++)
    {
      min = a[i];
      tmp = i;
      for (j = i; j < b-1; j++) 
      {
        if (min > a[j]) 
        {
           min = a[j];
           tmp = j;
        }
      }
      a[tmp] = a[i];
      a[i] = min;
      if (i > 0) 
      {
        if (a[i-2] != a[i] && a[i] == a[i-1]) printf("%d\n", a[i]);
      }   
    }

    return 0;
  };

Sorting logic is inefficient. Shouldn't `j=i` be `j=i+1`? And correspondingly `i — Aditi Rawat, Nov 17 '17 at 10:42
Okay if you wish to stick with this only though you are making unnecessary comparisons. Your current logic has **O(n^2)** complexity. A lot of sorts give better time complexity than this. — Aditi Rawat, Nov 17 '17 at 10:45
Do i need to sort first array at all? Maybe just answers array — Andrew Moskovets, Nov 17 '17 at 10:50
The specification names the number of lotteries `n` but you re-name this `b` in your program. Why, are you trying to confuse the reader on purpose? Overall, give your variables _meaningful_ names, not a, b, c. Also, allocating 100,000 integers on the stack is a really bad idea, see this: https://stackoverflow.com/questions/571945/getting-a-stack-overflow-exception-when-declaring-a-large-array. As for the sorting algorithm, do you have to re-invent the wheel? Is there a reason why you can't call `qsort`, or at the very least implement sorting yourself with quicksort or merge sort? — Lundin, Nov 17 '17 at 10:52

user2736738 · Accepted Answer · 2017-11-17T11:20:21.920

Your sorting algorithm has complexity O(n^2). For an input with size 10^5 it takes many magnitude more than O(nlogn) quick sort algorithm.

Here you can use qsort() to solve the problem.

qsort(a, b, sizeof int, cmp);

Where cmp is

int cmp(const void *a, const void *b)
{
    return (*(int *) a - *(int *) b);
}

The algorithm after sorting is much more simpler.

int p = a[0], ct=0;
for(size_t i = 1; i<=b-1; i++)
{
    if( a[i] == a[i-1])
       ct++;
    else{
       if( ct > 1){
       // a[i-1] should be printed.
       }
       ct = 1;
    }
}
if( ct > 1){
   //a[b-1] should also be print.
}

The idea is something like this

As the numbers are sorted we will get a monotonic sequence.

We compare every number with one that came before. If there is duplicate they will appear next to next.

We only collect those numbers which appear multiple times.

Also there are few things you can follow

Declaring large variables inside a method sometimes is constrained by the available memory(automatic storage duration).(may have stackoverflow etc) Make it global.(something of static storage duration).
The variable names are not a bit readable.
You can get help in case of using a sorting algorithm.
Knowing the complexity of different algorithms helps. The thing is in your case the complexity is O(n^2). The sorting algorithm better than this is the popular merge sort etc. This simple idea solves the problem in your case.

You can check yourself that this code is atleast a bit more readable than your version. This helps avoid small mistakes.

 int temp = a[0], count=0;
for(size_t i = 1; i<=len-1; i++)
{
    if( arr[i] == arr[i-1])
       count++;
    else{
       if( count > 1){
       // a[i-1] should be printed.
       }
       count = 1;
    }
}
if( count > 1){
   //arr[len-1] should also be print.
}

Write sorted in ascending order numbers that were drawn more than once. [ C ]

1 Answers1