Leetcode75/duplicateArray.cpp at main · kasakvaish/Leetcode75 · 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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ff                 first
#define ss                 second
#define endl               "\n"
#define ll                 long long
#define ld                 long double
#define loop(a, b, c)      for(ll (a) = (b); (a)<=(c); (a)++)
#define looprev(a, b, c)   for(ll (a) = (b); (a)>=(c); (a)--)
#define pb                 push_back
#define mp                 make_pair
#define pii                pair<ll, ll>
#define vi                 vector<ll>
#define mii                map<ll, ll>
#define ump                unordered_map<ll, ll>
#define pqb                priority_queue<ll>
#define pqs                priority_queue<int, vi, greater<ll> >
#define setbits(x)         __builtin_popcountll(x)
#define zrobits(x)         __builtin_ctzll(x)
#define mod                1000000007
#define inf                1e18
#define ps(x, y)           fixed<<setprecision(y)<<x
#define mk(arr,n,type)     type *arr = new type[n];
#define w(t)               int x; cin>>x; while(x--)
// mt19937                    rng(chrono::steady_clock::now,time_since_epoch(),count());
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void file_i_o(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	/* #ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif */
}


int findDuplicate(vector<int> &arr, int n){
	// Write your code here.

	// Approach 1

	/*sort(arr.begin(), arr.end());

	for(int i = 0; i < arr.size(); i++){
		if(arr[i] == arr[i+1])
			return arr[i];
	}

	return -1;*/


	// Approach 2

	/*for(int i = 0; i < arr.size(); i++){
		int idx = abs(arr[i]) - 1;
		if(arr[idx] < 0) {
			return idx + 1;
		}
		else {
			arr[idx] = -1*arr[idx];
		}
	}

	return -1;*/


	// Hare and Tortoise method

	int tortoise = arr[0];
	int hare = arr[0];

	do {
		// hare pointer move twice as tortoise

		tortoise = arr[tortoise];
		hare = arr[arr[hare]];


	}
	// find the intersection pt of two runners.
	while(tortoise != hare);
		// to find the entrance to the cycle torrtoise begins from start of array
	tortoise = arr[0];
	while(tortoise != hare) {
		// This time both runner move with same speed

		tortoise = arr[tortoise];
		hare = arr[hare];

	}
	// return the entrance to the cycle
	return hare;

}


int main(int argc, char const *argv[]) {

	file_i_o();

	clock_t start, end;
    start = clock();


    int n;
    cin >> n;

    vector<int> arr(n);

    for(int i = 0; i < n; i++) {
    	cin >> arr[i];
    }

    cout << findDuplicate(arr, n) << endl;


	end = clock();

	double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
    cerr<<"\nTime : "<<fixed<<time_taken<<setprecision(5)<<" s \n";
    cerr<<"\n"<< "Coded By : S!r Black-D3vil" <<"\n";

	return 0;
}