fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int singleNonDuplicate(vector<int>& nums) {
  7.         int n = nums.size();
  8.         int low=0;
  9.         int high=n-1;
  10.         int idx=n-1;
  11.  
  12.         if(n==1){
  13.             return nums[0];
  14.         }
  15.  
  16.  
  17.         while(low<high){
  18.           int mid = low+(high-low)/2;
  19.           if(mid%2!=0){
  20.             if(nums[mid]==nums[mid-1]){
  21.                 low=mid+1;
  22.             }
  23.             else{
  24.                 idx=mid;
  25.                 high=mid;
  26.  
  27.             }
  28.           }
  29.           else{
  30.               if(nums[mid]==nums[mid+1]){
  31.                 low=mid+1;
  32.               }
  33.               else{
  34.                 high=mid;
  35.                 idx=mid;
  36.               }
  37.           }
  38.         }
  39.  
  40.         return nums[idx];
  41.  
  42.  
  43.     }
  44.  
  45.  
  46. int main() {
  47. 	// your code goes here
  48. 	int n;
  49. 	cin>>n;
  50. 	vector<int> nums(n);
  51. 	for(int i=0;i<n;i++){
  52. 		cin>>nums[i];
  53. 	}
  54.  
  55. 	cout<<singleNonDuplicate(nums);
  56.  
  57. 	return 0;
  58. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
9
1 1 2 3 3 4 4 8 8
stdout
copy 
2
https://ideone.com/TTjbXN
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!