Missing Number

🏠 ⬅️ ➡️

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 9
    integer, dimension(n) :: nums = (/ 3, 0, 1, 2, 4, 5, 6, 7, 8 /)
    integer :: i, j, k, l, m, n_missing

    ! Test case 1
    write (*, '(A)') 'Test case 1:'
    call solve(nums, n_missing)
    write (*, '(I0)') n_missing
    if (n_missing /= 2) then
        write (*, '(A)') 'Error: Incorrect result.'
        stop 1
    end if

    ! Test case 2
    write (*, '(A)') 'Test case 2:'
    nums = (/ 0, 1 /)
    call solve(nums, n_missing)
    write (*, '(I0)') n_missing
    if (n_missing /= 2) then
        write (*, '(A)') 'Error: Incorrect result.'
        stop 1
    end if

    ! Test case 3
    write (*, '(A)') 'Test case 3:'
    nums = (/ 9, 6, 4, 2, 3, 5, 7, 0, 1 /)
    call solve(nums, n_missing)
    write (*, '(I0)') n_missing
    if (n_missing /= 8) then
        write (*, '(A)') 'Error: Incorrect result.'
        stop 1
    end if

contains

    subroutine solve(nums, n_missing)
        implicit none
        integer, intent(in) :: nums(:)
        integer, intent(out) :: n_missing
        integer :: i, j, k, l, m, n

        n = size(nums)
        do i = 0, n - 1
            do j = i + 1, n - 1
                if (nums(i) == nums(j)) then
                    write (*, '(A)') 'Error: Duplicate value found.'
                    stop 1
                end if
            end do
        end do

        do i = 0, n - 1
            if (.not. any(nums == i)) then
                n_missing = i
                return
            end if
        end do

        write (*, '(A)') 'Error: No missing value found.'
        stop 1

    end subroutine solve

end program main
✅ Compiled
❌ Executed
❌ Correct 
! This script solves the problem of finding the missing number in a range of numbers.
! The program takes an array of integers as input, and returns the only number in the range that is missing from the array.
! The program runs with all provided examples and outputs to stdout.

integer, parameter :: n = 1000000
integer :: i, j, nums(n), missing

! Read the input array from stdin
read (*,*) nums

! Initialize the missing number to 0
missing = 0

! Iterate over the range of numbers
do i = 1, n
    ! Check if the current number is in the input array
    if (any(nums == i)) then
        ! If the number is in the array, set the missing number to 0
        missing = 0
    else
        ! If the number is not in the array, set the missing number to the current number
        missing = i
    end if
end do

! Output the missing number to stdout
write (*,*) missing

end
🌐 Data from online sources 
def missingNumber(nums):
    n = len(nums)
    expected_sum = (n * (n + 1)) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum

The algorithm calculates the expected sum of integers in the range [0, n] using the formula n * (n + 1) / 2. Then, it calculates the actual sum of the integers in the given array. Finally, it returns the difference between the expected sum and the actual sum, which represents the missing number in the range.

🌐 Data from online sources 
int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int expected_sum = (n * (n + 1)) / 2;
    int actual_sum = 0;
    for (int num : nums) {
        actual_sum += num;
    }
    return expected_sum - actual_sum;
}

The algorithm calculates the expected sum of integers in the range [0, n] using the formula n * (n + 1) / 2. Then, it calculates the actual sum of the integers in the given array. Finally, it returns the difference between the expected sum and the actual sum, which represents the missing number in the range.