##### Welcome to Subscribe On Youtube
• /**

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

*/

public class Single_Element_in_a_Sorted_Array {

class Solution {
public int singleNonDuplicate(int[] nums) {

if (nums == null || nums.length == 0) {
return -1;
}

int start = 0, end = nums.length - 1;

while (start < end) {
// We want the first element of the middle pair,
// which should be at an even index if the left part is sorted.
// Example:
// Index: 0 1 2 3 4 5 6
// Array: 1 1 3 3 4 8 8
//            ^
int mid = (start + end) / 2;
if (mid % 2 == 1) mid--;

// We didn't find a pair. The single element must be on the left.
// (pipes mean start & end)
// Example: |0 1 1 3 3 6 6|
//               ^ ^
// Next:    |0 1 1|3 3 6 6
if (nums[mid] != nums[mid + 1]) end = mid;

// We found a pair. The single element must be on the right.
// Example: |1 1 3 3 5 6 6|
//               ^ ^
// Next:     1 1 3 3|5 6 6|
else start = mid + 2;
}

// 'start' should always be at the beginning of a pair.
// When 'start > end', start must be the single element.
return nums[start];
}
}
}

############

class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = (left + right) >> 1;
// if ((mid % 2 == 0 && nums[mid] != nums[mid + 1]) || (mid % 2 == 1 && nums[mid] !=
// nums[mid - 1])) {
if (nums[mid] != nums[mid ^ 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
}

• // OJ: https://leetcode.com/problems/single-element-in-a-sorted-array/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
int singleNonDuplicate(vector<int>& A) {
int L = 0, R = A.size() - 1;
while (L < R) {
int M = (L + R) / 2;
if ((M % 2 == 0 && A[M] == A[M + 1])
|| (M % 2 == 1 && A[M] == A[M - 1])) L = M + 1;
else R = M;
}
return A[L];
}
};

• class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) >> 1
# Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]):
if nums[mid] != nums[mid ^ 1]:
right = mid
else:
left = mid + 1
return nums[left]

############

class Solution(object):
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return reduce(lambda x, y: x^y, nums)

• func singleNonDuplicate(nums []int) int {
left, right := 0, len(nums)-1
for left < right {
mid := (left + right) >> 1
if nums[mid] != nums[mid^1] {
right = mid
} else {
left = mid + 1
}
}
return nums[left]
}

• function singleNonDuplicate(nums: number[]): number {
let left = 0,
right = nums.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] != nums[mid ^ 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}


• impl Solution {
pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
let mut l = 0;
let mut r = nums.len() - 1;
while l < r {
let mid = l + r >> 1;
if nums[mid] == nums[mid ^ 1] {
l = mid + 1;
} else {
r = mid;
}
}
nums[l]
}
}


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

############

class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = (left + right) >> 1;
// if ((mid % 2 == 0 && nums[mid] != nums[mid + 1]) || (mid % 2 == 1 && nums[mid] !=
// nums[mid - 1])) {
if (nums[mid] != nums[mid ^ 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
}

• // OJ: https://leetcode.com/problems/single-element-in-a-sorted-array/
// Time: O(logN)
// Space: O(1)
class Solution {
public:
int singleNonDuplicate(vector<int>& A) {
int L = 0, R = A.size() - 1;
while (L < R) {
int M = (L + R) / 2;
if ((M % 2 == 0 && A[M] == A[M + 1])
|| (M % 2 == 1 && A[M] == A[M - 1])) L = M + 1;
else R = M;
}
return A[L];
}
};

• class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) >> 1
# Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]):
if nums[mid] != nums[mid ^ 1]:
right = mid
else:
left = mid + 1
return nums[left]

############

class Solution(object):
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return reduce(lambda x, y: x^y, nums)

• func singleNonDuplicate(nums []int) int {
left, right := 0, len(nums)-1
for left < right {
mid := (left + right) >> 1
if nums[mid] != nums[mid^1] {
right = mid
} else {
left = mid + 1
}
}
return nums[left]
}

• function singleNonDuplicate(nums: number[]): number {
let left = 0,
right = nums.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] != nums[mid ^ 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}


• impl Solution {
pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
let mut l = 0;
let mut r = nums.len() - 1;
while l < r {
let mid = l + r >> 1;
if nums[mid] == nums[mid ^ 1] {
l = mid + 1;
} else {
r = mid;
}
}
nums[l]
}
}