Set Mismatch

🏠 ⬅️ ➡️

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Example 1:

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

Example 2:

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

Constraints:

  • 2 <= nums.length <= 104
  • 1 <= nums[i] <= 104
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

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

    ! Original set
    s = (/ (i, i=1,n) /)

    ! Error: one number got duplicated
    nums = (/ 1, 2, 2, 4, 5 /)

    call solve(nums)

contains

    subroutine solve(nums)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: repeated, missing

        repeated = find_repeated(nums)
        missing = find_missing(nums)

        write (*,*) 'Repeated: ', repeated
        write (*,*) 'Missing: ', missing

    end subroutine solve

    function find_repeated(nums) result(repeated)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: repeated
        logical :: found

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

    end function find_repeated

    function find_missing(nums) result(missing)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: missing
        logical :: found

        missing = 0
        do i = 1, size(nums)
            found = any(nums == i)
            if (.not. found) then
                missing = i
                exit
            end if
        end do

    end function find_missing

end program main
✅ Compiled
✅ Executed
❌ Correct 
module duplicate_and_missing

implicit none

contains

function find_duplicate_and_missing(nums) result(duplicate_and_missing)

integer, intent(in) :: nums(:)
integer :: duplicate_and_missing(2)

! Local variables
integer :: i, j, count

! Initialize the result array
duplicate_and_missing = 0

! Iterate over the input array
do i = 1, size(nums)

    ! Reset the count for each number
    count = 0

    ! Iterate over the input array again
    do j = 1, size(nums)

        ! If the current number matches the current number, increment the count
        if (nums(i) == nums(j)) then
            count = count + 1
        end if

        ! If the count is greater than 1, the number is a duplicate
        if (count > 1) then
            duplicate_and_missing(1) = nums(i)
            exit
        end if

    end do

    ! If the count is 0, the number is missing
    if (count == 0) then
        duplicate_and_missing(2) = nums(i)
        exit
    end if

end do

end function find_duplicate_and_missing

end module duplicate_and_missing

program test_duplicate_and_missing

use duplicate_and_missing

implicit none

! Test case 1:
print *, find_duplicate_and_missing([1, 2, 2, 4])
! Expected output: [2, 3]

! Test case 2:
print *, find_duplicate_and_missing([1, 1])
! Expected output: [1, 2]

end program test_duplicate_and_missing
🌐 Data from online sources 
def findErrorNums(nums):
    result = []
    for num in nums:
        index = abs(num) - 1
        if nums[index] > 0:
            nums[index] = -nums[index]
        else:
            result.append(index + 1)
    for i, num in enumerate(nums):
        if num > 0:
            result.append(i + 1)
            break
    return result
  1. Iterate through the given array, creating and using the index as the absolute value of the current number minus one. By doing this, we visit the indices in a specific order that allows us to mark numbers we have already visited.
  2. If the value at the index is positive, we negate it. If it's negative, it means we found the duplicate number. Store the duplicate number (index + 1) in the result array.
  3. Iterate through the array again to find the first positive value. This index plus one will be the missing number, as others should have been negated in the previous steps.
  4. Add the missing number to the result array and return it.
🌐 Data from online sources 
#include <vector>
using namespace std;

vector<int> findErrorNums(vector<int>& nums) {
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        int index = abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        } else {
            result.push_back(index + 1);
        }
    }
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0) {
            result.push_back(i + 1);
            break;
        }
    }
    return result;
}
  1. Iterate through the given array, creating and using the index as the absolute value of the current number minus one. By doing this, we visit the indices in a specific order that allows us to mark numbers we have already visited.
  2. If the value at the index is positive, we negate it. If it's negative, it means we found the duplicate number. Store the duplicate number (index + 1) in the result array.
  3. Iterate through the array again to find the first positive value. This index plus one will be the missing number, as others should have been negated in the previous steps.
  4. Add the missing number to the result array and return it.