⬅ Previous Topic
Capacity to Ship Packages within D DaysNext Topic ⮕
Aggressive Cows Problem⬅ Previous Topic
Capacity to Ship Packages within D DaysNext Topic ⮕
Aggressive Cows ProblemTopic Contents
You're given a sorted array of unique positive integers and an integer k
. The array is strictly increasing, but it may be missing some positive numbers. Your task is to find the kth missing positive number in the sequence.
The array only contains some of the positive integers starting from 1, and some numbers are missing. You must figure out what the kth
missing number would be if we continued counting all the positive numbers in order.
If the array is empty, then the answer is simply k
because all numbers are missing.
low = 0
and high = arr.length - 1
.low ≤ high
:mid = low + (high - low) / 2
.missing = arr[mid] - (mid + 1)
.missing < k
, search right side by setting low = mid + 1
.high = mid - 1
.low + k
as the answer.public class KthMissingNumber {
public static int findKthPositive(int[] arr, int k) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int missing = arr[mid] - (mid + 1); // How many numbers are missing before index mid
if (missing < k) {
low = mid + 1; // We need to move right to find more missing numbers
} else {
high = mid - 1; // Too many missing, move left
}
}
return low + k; // kth missing number is after low numbers in total
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 7, 11};
int k = 5;
System.out.println("Kth missing number is: " + findKthPositive(arr, k));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | The target is found in the first binary search step. |
Average Case | O(log n) | Binary search halves the search space at each step, making it efficient even for large arrays. |
Worst Case | O(log n) | At most, the search checks log(n) elements until the missing count reaches or exceeds k. |
O(1)
Explanation: The algorithm only uses a constant number of variables regardless of input size.
⬅ Previous Topic
Capacity to Ship Packages within D DaysNext Topic ⮕
Aggressive Cows ProblemYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.