137. Single Number II

Description

The singleNumber function aims to find the unique number in a list where every other number appears exactly twice.

Intuition

In a list where every number except one appears twice, the unique number is the one that does not have a duplicate. To find this unique number, the function examines each number and checks if it appears again in the rest of the list. If a number is found to be unique, it is returned.

Approach

1. Iterate through each element: Use a for loop to go through each element in the list.
2. Check for duplicates: For each element, use a nested while loop to check if it appears again in the rest of the list.
3. Determine uniqueness: If the element is not found again in the list, return it as the unique number.
4. Handle constraints: The function assumes that there is exactly one unique number in the list, so a return value of -1 is added to handle edge cases (though this line should never be reached given the problem constraints).

Complexity

Time Complexity**:

(O(n^2)) due to the nested loops used to check for duplicates.

Space Complexity**:

(O(1)) as the function uses only a few extra variables for computation.

Code

C++

class Solution {
public:
    int singleNumber(vector& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            bool foundDuplicate = false;
            for (int j = 0; j < nums.size(); ++j) {
                if (nums[i] == nums[j] && i != j) {
                    foundDuplicate = true;
                    break;
                }
            }
            if (!foundDuplicate) {
                return nums[i];
            }
        }
        return -1; // If no single number found
    }
};

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            j = 0
            while j < len(nums):
                if nums[i] == nums[j] and i != j:
                    break
                j += 1
            if j == len(nums):
                return nums[i]
        return -1  # This line should never be reached as per problem constraints

Java

class Solution {
    public int singleNumber(int[] nums) {
        int i = 0;
        int j = 0;

        while (i < nums.length) {
            j = 0;

            while (j < nums.length) {
                if (nums[i] == nums[j] && i != j) {
                    break;
                }
                j++;
            }

            if (j == nums.length) {
                return nums[i];
            }
            i++;
        }

        return -1; // Should never reach here since the problem guarantees a solution
    }
}

JavaScript

var singleNumber = function(nums) {
  let i = 0;
  let j = 0;

  for (; i < nums.length; i++) {
      j = 0;

      do {
          if (nums[i] === nums[j] && i !== j)
              break;

          j++;
      }
      while (j < nums.length)

      if (j === nums.length)
          return nums[i];
  }
};