The problem you’re tackling involves finding the missing numbers in an array where the elements are in the range [1, n]. The idea is to identify the numbers that do not appear in the array, and we can do this efficiently in O(n) time and O(1) extra space.

Approach Explanation:

1. Input and Constraints:

   • The array contains integers in the range [1, n], where n is the length of the array.
   • The goal is to identify which numbers in this range are missing from the array.

2. Efficient Approach:

   • No extra space: Instead of using a secondary array or hash map, we can use the input array itself to mark numbers we’ve already encountered.
   • Marking visited numbers:
     • For each number nums[i], we treat its absolute value minus one as an index.
     • If the value at that index is positive, we flip it to negative, marking that the number corresponding to the index has been seen.
     • If a number is missing, the value at its corresponding index will remain positive.

3. Key Observations:

   • By flipping the values at corresponding indices to negative, we keep track of the elements that are present in the array.
   • After the iteration, any index that still holds a positive value represents a missing number.

Code Implementation:

#include <stdio.h>

int Abs(int num)
{
    return (num < 0) ? -num : num;
}

void findMissedNumbers(int nums[], int n)
{
    // Mark visited numbers by flipping values to negative
    for (int i = 0; i < n; i++)
    {
        int index = Abs(nums[i]) - 1; // Get the index based on the value
        if (nums[index] > 0)
        {
            nums[index] = -nums[index]; // Mark the number as visited
        }
    }

    // Print missing numbers
    printf("Missed Numbers: ");
    for (int i = 0; i < n; i++)
    {
        if (nums[i] > 0) // If the number at index is positive, it's missing
        {
            printf("%d ", i + 1); // The missing number is i + 1
        }
    }
    printf("n");
}

int main()
{
    int nums[] = {4, 3, 2, 7, 8, 2, 3, 1};
    int n = sizeof(nums) / sizeof(nums[0]);

    findMissedNumbers(nums, n); // Call the function to find missing numbers

    return 0;
}

Explanation of the Code:

1. Abs Function:

   • This function returns the absolute value of a number. It’s used to get the correct index when marking elements in the array.

2. findMissedNumbers Function:

   • The loop iterates over the array, and for each element nums[i], it calculates the index corresponding to the number nums[i] by using the formula index = Abs(nums[i]) - 1.
   • If the value at this index is positive, we mark it by flipping the value at that index to negative. This means we’ve encountered the number corresponding to that index.
   • After processing the array, any index that has a positive value indicates the number i + 1 is missing from the array.

3. Output:

   • The missing numbers are printed as the result.

Example:

For the input array:
[4, 3, 2, 7, 8, 2, 3, 1]

• Steps:

  • Mark 1 as encountered by flipping the value at index 0.
  • Mark 2 as encountered by flipping the value at index 1.
  • Mark 3 as encountered by flipping the value at index 2.
  • Mark 4 as encountered by flipping the value at index 3.
  • Mark 7 as encountered by flipping the value at index 6.
  • Mark 8 as encountered by flipping the value at index 7.

• After processing the array, the numbers that remain unmarked (positive values) are 5 and 6, so the output will be:

Output:

Missed Numbers: 5 6

Time Complexity:

• Time Complexity: O(n) because we iterate through the array once to mark the elements and another time to identify the missing numbers.
• Space Complexity: O(1) extra space, since we modify the input array in place and do not use any additional data structures.