540

1 files changed, 39 insertions, 0 deletions

diff --git a/540/main.py b/540/main.py
new file mode 100755
index 0000000..29cc1d3
--- /dev/null
+++ b/540/main.py
@@ -0,0 +1,39 @@
+#!/usr/bin/env python
+from typing import List
+
+
+class Solution:
+    def singleNonDuplicate(self, nums: List[int]) -> int:
+        start = 0
+        end = len(nums) - 1
+        mid = 0
+
+        if len(nums) == 1:
+            return nums[0]
+
+        while start < end:
+            mid = (start + end) // 2
+            if nums[mid] == nums[mid + 1]:
+                if (end - mid + 1) % 2 == 0:
+                    end = mid - 1
+                else:
+                    start = mid
+            elif nums[mid] == nums[mid - 1]:
+                if (mid - start + 1) % 2 == 0:
+                    start = mid + 1
+                else:
+                    end = mid
+            else:
+                return nums[mid]
+
+        return nums[end]
+
+
+if __name__ == "__main__":
+    solution = Solution()
+    assert solution.singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]) == 2
+    assert solution.singleNonDuplicate([3, 3, 7, 7, 10, 11, 11]) == 10
+    assert solution.singleNonDuplicate([1, 2, 2, 3, 3, 4, 4, 8, 8]) == 1
+    assert solution.singleNonDuplicate([1, 1, 2, 2, 3, 3, 4, 4, 8]) == 8
+    assert solution.singleNonDuplicate([1, 1, 2]) == 2
+    assert solution.singleNonDuplicate([0, 1, 1, 2, 2, 5, 5]) == 0