QuestionsRandom/missingNumbers.cpp at master · Snigdha7906/QuestionsRandom · GitHub

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?*/

#include<bits/stdc++.h>
using namespace std;

// int missingNumber1(vector<int> nums)
// {
// 	int mn;
//     sort(nums.begin(),nums.end());
// 	for(int i=0; i<nums.size(); i++)
// 	{
//         if(nums[0]!=0)
// 		{
// 			mn= 0;
//             break;
// 		}
// 		else if( nums[i+1]!= nums[i]+1 )
// 		{
// 			mn=nums[i]+1;
// 			break;
// 		}
//         else{
//             mn=nums[nums.size() -1] +1;
//         }

// 	}
// 	return mn;
// }

int missingNumber1(vector<int> nums) //O(nlogn)
{
	sort(nums.begin(),nums.end());
	int i;
	for(i=0;i<nums.size();i++)
	{
		if(nums[i]!= i)
			return i;
	}

	return i;
}
int missingNumber2(vector<int> nums) //sum approach  O(n)
{
	int sum=0;   // 0 5 2 1 3  sum= 0
	for(int i=0;i<nums.size();i++){
		sum=sum+i;							//0 1   -4+2   -4+3   -2+4
		sum=sum-nums[i]	;					//0 -4	-2-2	-1-1	2-3 =-1
	}
	sum=sum+nums.size();								//sum=sum+nums.size()   -1+5=4
	return sum;
}
int main()
{
	int x,n;
	cin>>n;
	vector<int> nums;
	for(int i=0;i<n;i++){
		cin>>x;
		nums.push_back(x);
	}
	cout<<"Missing number: "<<missingNumber1(nums)<<endl;
	cout<<"Missing number: "<<missingNumber2(nums)<<endl;
	return 0;
}