old_contents: # Time:  O(n)
  # Space: O(1)
  
  class Solution(object):
      def findDuplicate(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          duplicate = 0
          # Mark the value as visited by negative.
          for num in nums:
              if nums[abs(num) - 1] > 0:
                  nums[abs(num) - 1] *= -1
              else:
                  duplicate = abs(num)
                  break
          # Rollback the value.
          for num in nums:
              if nums[abs(num) - 1] < 0:
                  nums[abs(num) - 1] *= -1
              else:
                  break
          return duplicate
  
new_contents: # Time:  O(nlogn)
  # Space: O(1)
  
  class Solution(object):
      def findDuplicate(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          left, right = 1, len(nums) - 1
  
          while left <= right:
              mid = left + (right - left) / 2
              # Get count of num <= mid.
              count = 0
              for num in nums:
                  if num <= mid:
                      count += 1
              if count > mid:
                  right = mid - 1 
              else:
                  left = mid + 1
          return left
  
  # Time:  O(n)
  # Space: O(n)
  class Solution2(object):
      def findDuplicate(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          """
          duplicate = 0
          # Mark the value as visited by negative.
          for num in nums:
              if nums[abs(num) - 1] > 0:
                  nums[abs(num) - 1] *= -1
              else:
                  duplicate = abs(num)
                  break
          # Rollback the value.
          for num in nums:
              if nums[abs(num) - 1] < 0:
                  nums[abs(num) - 1] *= -1
              else:
                  break
          return duplicate
  
subject: Update find-the-duplicate-number.py