🎨 Try our Free AI Image Generation Feature

137. Single Number II

avatar
Dare2Solve

11 months ago

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];
  }
};