Single Number

🏠 ⬅️ ➡️

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1] Output: 1

Example 2:

Input: nums = [4,1,2,1,2] Output: 4

Example 3:

Input: nums = [1] Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: nums
    integer :: i

    ! Example 1
    nums = [2, 2, 1]
    call solve(nums)
    print '(A, I0)', 'Example 1: ', nums(1)

    ! Example 2
    nums = [4, 1, 2, 1, 2]
    call solve(nums)
    print '(A, I0)', 'Example 2: ', nums(1)

    ! Example 3
    nums = [1]
    call solve(nums)
    print '(A, I0)', 'Example 3: ', nums(1)

contains

    subroutine solve(nums)
        implicit none
        integer, dimension(:), intent(inout) :: nums
        integer :: i, j

        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) == nums(j)) then
                    nums(i) = 0
                    exit
                end if
            end do
        end do

        do i = 1, size(nums)
            if (nums(i) /= 0) then
                nums(1) = nums(i)
                return
            end if
        end do
    end subroutine solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module FindSingleNumber
    implicit none
    private
    public :: find_single_number
contains
    function find_single_number(nums) result(single_number)
        integer, intent(in) :: nums(:)
        integer :: single_number
        integer :: i, j, temp

        ! Sort the array in ascending order
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) > nums(j)) then
                    temp = nums(i)
                    nums(i) = nums(j)
                    nums(j) = temp
                end if
            end do
        end do

        ! Find the first element that appears only once
        single_number = nums(1)
        do i = 2, size(nums)
            if (nums(i) /= nums(i - 1)) then
                exit
            end if
        end do

    end function find_single_number
end module FindSingleNumber

program test_find_single_number
    use FindSingleNumber
    implicit none
    integer, parameter :: nums1(3) = [2, 2, 1]
    integer, parameter :: nums2(5) = [4, 1, 2, 1, 2]
    integer, parameter :: nums3(1) = [1]
    integer :: single_number

    single_number = find_single_number(nums1)
    write (*,*) "Example 1:", single_number

    single_number = find_single_number(nums2)
    write (*,*) "Example 2:", single_number

    single_number = find_single_number(nums3)
    write (*,*) "Example 3:", single_number
end program test_find_single_number
🌐 Data from online sources 
def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

The algorithm utilizes the XOR bitwise operation. XOR is a binary operation that outputs 1 when the inputs differ and 0 when the inputs are the same.

To find the single element that appears once in the array, we XOR all elements in the array. Since every pair of identical numbers will cancel each other out as a ^ a = 0, the remaining XOR result would be the single unique number, as 0 ^ a = a.

The algorithm processes the array once, giving it a linear time complexity of O(n), and only requires a constant amount of extra space to store the result variable, satisfying the requirements.

🌐 Data from online sources 
int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

The algorithm utilizes the XOR bitwise operation. XOR is a binary operation that outputs 1 when the inputs differ and 0 when the inputs are the same.

To find the single element that appears once in the array, we XOR all elements in the array. Since every pair of identical numbers will cancel each other out as a ^ a = 0, the remaining XOR result would be the single unique number, as 0 ^ a = a.

The algorithm processes the array once, giving it a linear time complexity of O(n), and only requires a constant amount of extra space to store the result variable, satisfying the requirements.