-
Notifications
You must be signed in to change notification settings - Fork 1
/
element that appears once.cpp
114 lines (85 loc) Β· 2.45 KB
/
element that appears once.cpp
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
/*
///////////////////////////////////////////
//Question/Info
Find the element that appears once in sorted array
Basic Accuracy: 58.65% Submissions: 4242 Points: 1
Given a sorted array arr[] of size N. Find the element that appears only once in the array. All other elements appear exactly twice.
Example 1:
Input:
N = 11
arr[] = {1, 1, 2, 2, 3, 3, 4, 50, 50, 65, 65}
Output: 4
Explanation: 4 is the only element that
appears exactly once.
Your Task:
You don't need to read input or print anything. Complete the function findOnce() which takes sorted array and its size as its input parameter and returns the element that appears only once.
Expected Time Complexity: O(log N)
Expected Auxiliary Space: O(1)
Constraints:
-105 <= N <= 105
Company Tags
Amazon D-E-Shaw Ola Cabs
author: srj_v
///////////////////////////////////////////
*/
#include <bits/stdc++.h>
using namespace std;
// #define int long long int
#define sbit(x) __builtin_popcount(x)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define eb(x) emplace_back(x)
#define ct(x) cout << x << "\n";
#define ct2(x,y) cout << x << " " << y << "\n";
#define tc(x) cout << x << " ";
#define tc2(x,y) cout << x << " " << y << " ";
#define forn(i,n) for(int i = 0; i < (int)(n); ++i)
#define forx(i,x,n) for(int i = x; i < (int)(n); ++i)
#define nfor(i,n) for(int i = n-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define fsp(x,y) fixed << setprecision(y) << x
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007 // (1e9+7)
#define pii pair<int,int>
#define pis pair<int,string>
#define vi vector<int>
#define vii vector<pii>
#define mii map<int,int>
#define p_q priority_queue // priority_queue<int> (&) priority_queue< int,vi,greater<int> >
#define _IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long double ld;
typedef long long int lli;
#pragma GCC optimize("Ofast")
void c_p_c()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int32_t main() {
///////////
c_p_c();
///////////
_IOS
//////////
// code
/*
int t ; cin >> t; while(t--){}
*/
class Solution
{
public:
int findOnce(int arr[], int n)
{
//code here.
int x = arr[0];
for (auto i = 1 ; i < n ; i++) {
x = x ^ arr[i];
}
return x ;
}
};
// cerr << "time: " << clock() << " ms" << '\n';
return 0;
}