Kth Missing Positive Number in Java
In this article, we will look at the Kth Missing Positive Number in Java. The Kth Missing Positive Number problem entails determining the Kth missing positive integer in a series of positive integers. This is normally given an array containing a sorted or unsorted series of positive numbers.
Example 1: [Sorted Array]
Input: array = [2, 4, 7, 9, 10], K = 3
Output: The missing number is: 5
Explanation: The missing positive digits in the provided array are [1, 3, 5, 6, 8].
1 (missing; count = 1)
2 (Not missing)
3 (missing; count = 2)
4 (not missing)
5 (missing, count=3)
6 (missing; count = 4)
We stop when we reach the Kth missing positive number, which in this case is 3 (K = 3).
The 3rd missing positive number is 5.
So, for the provided sorted array [2, 4, 7, 9, 10] with K=3, the solution is 5 because it is the third missing positive integer in the series.
Example 2: [Unsorted Array]
Input: array = [3, 8, 1, 7, 10], K = 4
Output: The missing number is: 6
Explanation: The missing positive numbers in the provided array are [2, 4, 5, 6, 9].
1 (missing, count=1)
2 (not missing)
3 (not missing)
4 (missing, count=2)
5 (missing, count=3)
6 (missing, count=4)
We stop when we reach the Kth missing positive number, which in this case is 4 (K = 4).
The 4th missing positive number is 6.
So, for the unsorted array [3, 8, 1, 7, 10] with K=4, the solution is 6 because it is the fourth missing positive integer in the series.
Approach: Brute Force Approach [Sorted Array]
In the method missingK(), the loop iterates through the array, incrementing a counter (K) for each element less than or equal to it, and exiting the loop when an element bigger than K appears. The final value of K is then returned, indicating the Kth missing positive number.
FileName: KthMissingPositiveNumber1.java
public class KthMissingPositiveNumber1 {
public static int missingK(int[] array, int n, int K) {
for (int i = 0; i < n; i++) {
if (array[i] <= K) K++; // Shifting K
else break;
}
return K;
}
public static void main(String[] args) {
int[] array = {2, 4, 7, 9, 10};
int n = 5, K =3;
int ans = missingK(array, n, K);
System.out.println("The missing number is: " + ans);
}
}
Output:
The missing number is: 5
Complexity Analysis:
The provided code has a time complexity of O(n), where n is the size of the input array. The algorithm iterates through the array once, increasing the value of K for entries less than or equal to it. The space complexity is O(1) since the algorithm consumes a fixed amount of extra space.
Approach: Brute Force Approach [Unsorted Array]
It first sorts the array before iterating through it, incrementing a counter ('K') for each element that is less than or equal to it. The loop terminates when an element greater than 'K' is encountered. The final value of 'K' is returned, indicating the Kth missing positive number.
FileName: KthMissingPositiveNumber2.java
import java.util.Arrays;
public class KthMissingPositiveNumber2 {
public static int missingK(int[] array, int n, int K) {
Arrays.sort(array); // Sort the array
for (int i = 0; i < n; i++) {
if (array[i] <= K) K++; // Shifting K
else break;
}
return K;
}
public static void main(String[] args) {
int[] array = {3, 8, 1, 7, 10};
int n = 5, K = 4;
int ans = missingK(array, n, K);
System.out.println("The missing number is: " + ans);
}
}
Output:
The missing number is: 6
Complexity Analysis:
The time complexity is O(n log n) due to the sorting step using Arrays.sort(array). The succeeding linear iteration across the sorted array takes O(n). The space complexity is O(1) since the algorithm consumes a fixed amount of extra space.
Approach: Binary Search [Sorted Array]
In the method missingK(), the loop uses a binary search to compare the differences between each array element and its predicted place. It modifies the search range depending on whether the number of missing numbers is fewer than K. The outcome is K + high + 1, which reflects the Kth missing positive number.
FileName: KthMissingPositiveNumber3.java
public class KthMissingPositiveNumber3 {
public static int missingK(int[] array, int n, int K) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
int missing = array[mid] - (mid + 1);
if (missing < K) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return K + high + 1;
}
public static void main(String[] args) {
int[] array = {2, 4, 7, 9, 10};
int n = 5, K = 3;
int ans = missingK(array, n, K);
System.out.println("The missing number is: " + ans);
}
}
Output:
The missing number is: 5
Complexity Analysis:
The provided code has a time complexity of O(log n), where 'n' represents the size of the input array. This is because the technique uses binary search to find the position of the Kth missing positive value efficiently. The space complexity is O(1) because the method makes regular use of extra space, particularly for variables like 'low', 'high', and 'mid'.
Approach: Set-Based Enumeration [Unsorted Array]
Unique elements from the array are saved in the HashSet named missing. The procedure iterates through the array's minimum and maximum values, incrementing a counter (count) for each missing member that is not in the HashSet. When the count reaches the specified K, the corresponding missing number is returned. If the Kth missing element is not discovered within the supplied range, the function returns -1.
FileName: KthMissingPositiveNumber4.java
import java.util.Arrays;
import java.util.HashSet;
class KthMissingPositiveNumber4 {
static int findKth(int array[], int n, int K) {
HashSet<Integer> missing = new HashSet<>();
int count = 0;
for (int i = 0; i < n; i++) {
missing.add(array[i]);
}
// Find the maximum and minimum element
int maxm = Arrays.stream(array).max().getAsInt();
int minm = Arrays.stream(array).min().getAsInt();
// Traverse from the minimum to maximum element
for (int i = minm + 1; i < maxm; i++) {
// Check if "i" is missing
if (!missing.contains(i)) {
count++;
}
// Check if it is Kth missing
if (count == K) {
return i;
}
}
// If no Kth element is missing
return -1;
}
public static void main(String[] args) {
int array[] = {3, 8, 1, 7, 10};
int n = array.length;
int K = 4;
int ans = findKth(array, n, K);
System.out.println("The missing number is: " + ans);
}
}
Output:
The missing number is: 6
Complexity Analysis:
The time complexity is O(N + M), where N is the size of the array and M is the difference between the maximum and minimum values. Because the HashSet contains only unique elements, its space complexity is O(N). Without using explicit iterations, the algorithm efficiently finds the Kth missing positive number.