StriverSdeSheet/11.missing_repeating.cpp at main · devansha939/StriverSdeSheet · 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//using hashing
#include <bits/stdc++.h>

pair<int,int> missingAndRepeating(vector<int> &arr, int n)
{
	// Write your code here
	vector<int>vec(n+1,0);
	int temp{},temp2;
	for(int i=0;i<n;i++){
		vec[arr[i]]++;
		if(vec[arr[i]]>1)temp=arr[i];
	}
	for(int i=1;i<=n;i++){
		if(vec[i]==0)temp2=i;
	}

	return {temp2,temp};
}

// using maths


// using bit manipulation
#include <bits/stdc++.h>

pair<int,int> missingAndRepeating(vector<int> &arr, int n)
{
	// Write your code here
	int xr=0;
	for(int i=0;i<n;i++){
		xr^=arr[i];
		xr^=(i+1);
	}

	int firs_set_bit=0;
	while(1){
		if((xr&(1<<firs_set_bit))){
			break;
		}
		firs_set_bit++;
	}

	int zero{},one{};
	for(int i=0;i<n;i++){
		if((arr[i]&(1<<firs_set_bit))!=0){
			one^=arr[i];
		}
		else{
			zero^=arr[i];
		}
	}

	for(int i=1;i<=n;i++){
		if((i&(1<<firs_set_bit))!=0){
			one^=i;
		}
		else{
			zero^=i;
		}
	}

	int count{};
	for(int i=0;i<n;i++){
		if(arr[i]==zero){
			count++;
		}
	}

	if(count==2)return {one,zero};
	else return {zero,one};

}


// using bit manipulation but finding first set directly using property
#include <bits/stdc++.h>

pair<int,int> missingAndRepeating(vector<int> &arr, int n)
{
	// Write your code here
	int xr=0;
	for(int i=0;i<n;i++){
		xr^=arr[i];
		xr^=(i+1);
	}

	int firs_set_bit= xr & ~(xr-1);

	int zero{},one{};
	for(int i=0;i<n;i++){
		if((arr[i]&(firs_set_bit))!=0){
			one^=arr[i];
		}
		else{
			zero^=arr[i];
		}
	}

	for(int i=1;i<=n;i++){
		if((i&(firs_set_bit))!=0){
			one^=i;
		}
		else{
			zero^=i;
		}
	}

	int count{};
	for(int i=0;i<n;i++){
		if(arr[i]==zero){
			count++;
		}
	}

	if(count==2)return {one,zero};
	else return {zero,one};

}