# LintCode: Single Number IV

Single Number IV Similar Problems:

Give an array, all the numbers appear twice except one number which appears once and all the numbers which appear twice are next to each other. Find the number which appears once.

Notice

• 1 <= nums.length < 10^4
• In order to limit the time complexity of the program, your program will run 10^5 times.

Example

```Given nums = [3,3,2,2,4,5,5], return 4.

Explanation:

4 appears only once.
```
```Given nums = [2,1,1,3,3], return 2.

Explanation:
2 appears only once.
```

Github: code.dennyzhang.com

Credits To: LintCode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/single-number-iv
class Solution:
"""
@param nums: The number array
@return: Return the single number
"""
def getSingleNumber(self, nums):
## Basic Ideas: binary search
## Complexity: Time O(log(n)), Space O(1)
length = len(nums)
if length == 1: return nums
# two corner cases
if nums != nums: return nums
if nums[-1] != nums[-2]: return nums[-1]

left, right = 0, length-1
while left < right:
mid = left + (right-left)/2
if nums[mid] != nums[mid-1] and nums[mid] != nums[mid+1]:
return nums[mid]

# same with left
if nums[mid] == nums[mid-1]:
if (mid-1) % 2 == 0:
# right half
left = mid + 1
else:
right = mid - 2
else:
if mid % 2 == 0:
# right half
left = mid + 2
else:
right = mid - 1

# left equals right
return nums[left]
```

Share It, If You Like It.