C++

Forum

 
time complexicity problem in the code

samarth123 (53)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include "bits/stdc++.h"
#include <stdlib.h>
using namespace std;
 
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
 int main()
 {
 	int n,m;
 	cin>>n;
 	int a[n];
 	for(int i=0;i<n;i++)
 	{
 		cin>>a[i];
	}
     qsort(a,n,sizeof(int),compare);
     int count[n+1]={0};
	 for(int i=0;i<=n;i++)
     {
     	for(int j=0;j<n;j++)
     	{
     	 if(a[j]==i)
		  {
		  count[i]++;	
		  }	
		}
	 }
	 for(int i=0;i<=n;i++)
	 {
	 	if(count[i]==0)
	 	{
	 		cout<<i<<" ";
		}
	 }
 }

In this problem i want to find the missing terms in the array and then print those terms.
The array will consist numbers from 0 to n(both inclusive).
I have to print the missing numbers in that array.
For example-
Array consist of 7 elements [0 ,1, 5, 5, 4, 3, 2].So the answer for this example will be -> 6 , 7 beacuse these two numbers are not present in that array.
Next example -
A[]={4, 4 ,3, 0, 1, 2}
answer -> 5,6.
I did it in O(n^2) complexicity.
I want to find the solution in O(n) complexicity.
Please help me..!!

Stalker (77)
First of all you cannot create an array like this on line 13. Rather you must use a constant value to create the array like:

1
2
 
const int SIZE = 40;
int array[SIZE];


Another possibility if you don't know the size of the array, then you can use STL containers like std::vector. A container can increase in size as required by the user. You can learn more about containers here: http://www.cplusplus.com/reference/stl/

Once you have a sorted array or a container in ascending order. Then you can create another array with all the possible numbers and then subtract those that are already present in the original array.
Duthomhas (13206)
While Stalker's advice about line 13 is technically correct, the GCC does allow VLAs like this. Nevertheless, I agree with the instruction. For a general purpose container, create an array and track its size:

1
2
3
 
constexpr int MAX_SIZE = 40;
int numbers[ MAX_SIZE ];
int used = 0;
1
2
 
// add '4' to the end of the array
numbers[ used++ ] = 4;
1
2
3
 
// print the array
for (int n = 0; n < used; n++)
  cout << numbers[ n ] << "\n";
etc.

Now, on to your actual issue: O(n²) complexity. This happens because you have to loop over the array for every number, just to determine whether or not it is present. You can reduce complexity by improving the "is it present" test.


The first idea that comes to mind is to sort your data. This can easily be done in less than O(n²) time. Once done, you only need a linear O(n) pass over it to get the missing numbers. Your time is now the same as whatever it took to sort your array [O(n log n) for std::sort() → O(n log n)+O(n) → O(n log n)].


If your range of values is sufficiently small, however, you can reduce it to O(3n) → O(n) time by using the values as indices into the array.

O(n): create/fill the array with zeros
O(n): read the numbers, adding 1 to array[n] for every n you read.
O(n): scan through the array, printing out all the ns that have a count of 0.

Hope this helps.
samarth123 (53)
@Duoas .
Thanks for the idea :)
I solved it .
Topic archived. No new replies allowed.