aboutsummaryrefslogtreecommitdiff
path: root/single_element_sorted_arr.cpp
blob: e9bd894574dd073bd9c4af76b090c150a48d1eaf (plain)
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
// 540. Single Element in a Sorted Array
#include "leetcode.h"

/*
 * given a sorted array consisting of only integers where very element appears
 * exactly twice, except for one element which appears exactly once. return the
 * single element that appears only once. solution func must be o(ln) time and
 * o(1) space complexity.
 */

class Solution {
public:
  int singleNonDuplicate(vector<int> &nums) {
    int low = 0, high = nums.size() - 1, mid;
    while (low < high) {
      mid = (low + high) / 2;
      if ((mid % 2 && nums[mid - 1] == nums[mid]) ||
          (!(mid % 2) && nums[mid] == nums[mid + 1]))
        low = mid + 1;
      else
        high = mid;
    }
    return nums[low];
  }
};

int main() {
  Solution obj;
  vector<int> nums1 = {1, 1, 2, 3, 3, 4, 4, 8, 8},
              nums2 = {3, 3, 7, 7, 10, 11, 11};
  cout << obj.singleNonDuplicate(nums1) << endl; // expect: 2
  cout << obj.singleNonDuplicate(nums2) << endl; // expect: 10
}