1. Introduction
The K-th Missing in Natural Numbers problem is an array-based problem that can be solved efficiently using sorting and binary search.
We are given an array of distinct positive integers and a positive integer k. Our task is to find the K-th smallest positive integer that is not present in the given array.
Natural numbers start from 1, 2, 3, 4, 5, and continue infinitely.
Instead of checking every natural number one by one, we can calculate how many numbers are missing at each array position and use binary search to find the required answer efficiently.
2. Problem Statement
Given an array arr[] containing distinct positive integers and a positive integer k, remove all elements present in the array from the infinite sequence of natural numbers.
Find the K-th smallest number remaining in the sequence.
Example 1:
Input:
arr = [1, 9, 5, 2]
k = 6
Output:
10
Explanation:
First, sort the array:
[1, 2, 5, 9]
After removing these numbers from the natural number sequence:
3, 4, 6, 7, 8, 10, 11, ...
The 6th missing number is 10.
Example 2:
Input:
arr = [1, 2, 3, 4]
k = 1
Output:
5
Explanation:
After removing 1, 2, 3, and 4, the remaining sequence starts from 5.
Therefore, the first missing number is 5.
3. Approach: Sorting + Binary Search
The given array is not necessarily sorted. Therefore, our first step is to sort the array.
After sorting, we can calculate the number of missing positive integers before each array element.
Step 1: Sort the Array
Consider the input:
arr = [1, 9, 5, 2]
After sorting:
arr = [1, 2, 5, 9]
Step 2: Calculate the Number of Missing Elements
We use the following formula:
missing = arr[i] - (i + 1)
Why does this formula work?
At index i, the expected number is i + 1 because natural numbers start from 1.
However, the actual array element may be greater than the expected number.
The difference represents how many positive integers are missing before that element.
For example:
arr = [1, 2, 5, 9]
| Index | Array Element | Expected Number | Missing Count |
|---|
| 0 | 1 | 1 | 0 |
| 1 | 2 | 2 | 0 |
| 2 | 5 | 3 | 2 |
| 3 | 9 | 4 | 5 |
Therefore, the missing counts are:
0, 0, 2, 5
Step 3: Apply Binary Search
We need to find the first position where the missing count is greater than or equal to k.
Initialize:
int low = 0;
int high = arr.Length - 1;
Calculate the middle index:
int mid = low + (high - low) / 2;
Calculate missing numbers:
int missing = arr[mid] - (mid + 1);
Now check two conditions:
Condition 1:
If missing < k, the required number is further to the right.
low = mid + 1;
Condition 2:
If missing >= k, the required number may be at the current position or somewhere to the left.
high = mid - 1;
The binary search continues until low becomes greater than high.
Step 4: Find the Final Answer
After binary search, the answer is:
return low + k;
The reason is that low represents how many sorted array elements are at or before the boundary where the K-th missing number belongs.
Adding k gives the required missing positive integer.
4. Complete C# Code
class Solution
{
public int findKthSmall(int[] arr, int k)
{
// Step 1: Sort the array
Array.Sort(arr);
// Step 2: Initialize binary search
int low = 0;
int high = arr.Length - 1;
// Step 3: Apply binary search
while (low <= high)
{
int mid = low + (high - low) / 2;
// Count missing numbers
int missing = arr[mid] - (mid + 1);
if (missing < k)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
// Step 4: Return the K-th missing number
return low + k;
}
}
5. Dry Run
Let's understand the execution step by step.
Input:
arr = [1, 9, 5, 2]
k = 6
After sorting:
arr = [1, 2, 5, 9]
Initial values:
low = 0
high = 3
Iteration 1:
mid = 1
arr[mid] = 2
missing = 2 - (1 + 1)
missing = 0
Since 0 < 6, move to the right.
low = mid + 1
low = 2
Iteration 2:
low = 2
high = 3
mid = 2
arr[mid] = 5
missing = 5 - (2 + 1)
missing = 2
Since 2 < 6, move to the right.
low = mid + 1
low = 3
Iteration 3:
low = 3
high = 3
mid = 3
arr[mid] = 9
missing = 9 - (3 + 1)
missing = 5
Since 5 < 6, move to the right.
low = mid + 1
low = 4
Now:
low = 4
high = 3
The loop terminates because low > high.
Final calculation:
Answer = low + k
= 4 + 6
= 10
Output:
10
6. Complexity Analysis
Time Complexity: O(n log n)
- Sorting the array takes O(n log n).
- Binary search takes O(log n).
- Therefore, the overall time complexity is O(n log n).
Auxiliary Space Complexity: O(1)
We use only a few variables:
No additional array or collection is created by our algorithm. The sorting implementation is in-place for the standard .NET Array.Sort implementation, which uses O(log n) stack space in the worst case; therefore, the algorithm's explicit auxiliary space is O(1).
7. Important Concepts to Remember
- Sort the array before applying binary search.
- Use
arr[i] - (i + 1) to calculate the missing count. - If the missing count is smaller than
k, move right. - Otherwise, move left.
- Once binary search finishes, return
low + k.
8. Conclusion
The K-th Missing in Natural Numbers problem demonstrates how sorting and binary search can be combined to solve an array problem efficiently.
The most important part is understanding how to calculate the number of missing elements using:
missing = arr[i] - (i + 1)
Once this formula is clear, binary search helps us find the required position without checking every natural number individually.
This approach achieves O(n log n) overall time complexity and uses O(1) explicit auxiliary space.
Key takeaway: Remember these two formulas:
\[ missing = arr[mid] - (mid+1) \]
\[ Answer = low + k \]
These are the two important ideas behind this solution.
Arun PottiPosted Nov 16, 2026, 5:31 AM
Good Article.