Find the smallest missing number in c#

Programming C#
1

To find the smallest missing positive integer from an array in C#, you can use an efficient algorithm that operates in linear time (O(n)) and requires constant space (O(1)). The key idea is to use the input array itself to track which positive integers are present.

C# Code

using System;

class Program
{
    static int FindSmallestMissingPositive(int[] nums)
    {
        int n = nums.Length;

        // First, we want to put each number in its right place
        for (int i = 0; i < n; i++)
        {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
            {
                // Swap nums[i] with nums[nums[i] - 1]
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        // Now, we look for the first index where the number is not correct
        for (int i = 0; i < n; i++)
        {
            if (nums[i] != i + 1)
            {
                return i + 1; // The smallest missing positive integer
            }
        }

        // If all positions are correct, the smallest missing positive is n + 1
        return n + 1;
    }

    static void Main(string[] args)
    {
        int[] nums = { 3, 4, -1, 1 };
        int result = FindSmallestMissingPositive(nums);
        Console.WriteLine(result); // Output: 2
    }
}

Explanation

  1. Rearranging the Array: The first step is to rearrange the numbers in the array such that each number (x) is placed at index (x-1) if (x) is a positive integer and within the range of the array size (n).

    • The outer loop iterates through each element.
    • The inner while loop continues to swap the current element with the element at its target position (if they are not equal and valid) until the current number is either out of range or already in the correct position.

  2. Finding the Missing Number: After rearranging the array:

    • We iterate through the array again. The first index (i) where nums[i] is not equal to (i + 1) indicates that (i + 1) is the smallest missing positive integer.
    • If all elements are in their correct position, it means all numbers from 1 to (n) are present, and the smallest missing positive integer will be (n + 1).

Example Walkthrough

Consider the array {3, 4, -1, 1}:

  1. After Rearranging:

    • The first swap makes it {1, 4, -1, 3}.
    • The second swap gives {1, -1, 3, 4}.
    • Finally, it becomes {1, 4, -1, 3}.
    • The elements represent: 1 is at index 0, and we notice that index 1 has 4 (which should be 2).

  2. Finding the Missing Integer:

    • The check shows that index 1 does not have 2, so 2 is the smallest missing positive integer.

Benefits

  • Efficiency: The algorithm runs in linear time and does not require additional space, making it suitable for large datasets.
  • Simplicity: It leverages the properties of indexing and rearrangement, which is a clever way to solve the problem without using extra data structures.

This method effectively identifies the smallest missing positive integer with optimal performance.