Solution For Kth Missing Positive Number

Problem:

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The first missing positive integer is 1. The second missing positive integer is 5. The third missing positive integer is 6. The fourth missing positive integer is 8. The fifth missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The first missing positive integer is 5. The second missing positive integer is 6.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution:

To solve this problem, we can use binary search technique. We can search for the missing positive integer in the given array using binary search. We start the search from the mid of the array. We use a variable count to keep track of the number of missing positive integers found so far. We can check the number of missing positive integers on the left of the mid by subtracting the value of mid from the value at the mid-1 index. If the number of missing positive integers found so far is less than k, we can move the left index to the mid + 1. Otherwise, we can move the right index to the mid – 1.

We can return the value at the left index as the kth missing positive integer if we have found k missing positive integers. Otherwise, we can return the value at the right index as the kth missing positive integer.

Here is the code for the solution:

class Solution {
public:
int findKthPositive(vector& arr, int k) {
int n = arr.size();
int left = 0, right = n – 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int missing = arr[mid] - mid - 1;

        if (missing < k) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left + k;
}

};

Time Complexity: O(log N), where N is the length of the array.

Space Complexity: O(1).

Step by Step Implementation For Kth Missing Positive Number

class Solution {
    public int findKthPositive(int[] arr, int k) {
        // create a set to store all positive integers from the array
        Set set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }
        
        // iterate through all positive integers starting from 1
        // return the kth positive integer not present in the array
        int count = 0;
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            if (!set.contains(i)) {
                count++;
                if (count == k) {
                    return i;
                }
            }
        }
        
        // this line will never be reached
        return -1;
    }
}

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.



def find_kth_missing_positive(arr, k): 

# edge case: 
if len(arr) == 0: 
return k 

# initializing variables: 
missing_count = 0 
i = 0 

# iterating through the array: 
while i < len(arr): 

# if the current element is not k elements away from its expected position, 
# it is considered missing 
if arr[i] - i != 1: 
missing_count += 1 

# if the number of missing elements is equal to k, 
# then the kth missing positive is arr[i] - 1 
if missing_count == k: 
return arr[i] - 1 

# if the current element is less than its expected position, 
# then it is considered missing 
elif arr[i] <= 0 or arr[i] <= i: 
i += 1 

# if the current element is greater than its expected position, 
# then the next element is expected to be arr[i] + 1 
else: 
i += arr[i] - i - 1

var findKthPositive = function(arr, k) {
    
    // create a set from the input array
    let nums = new Set(arr);
    
    // start a counter at 1 (first positive number)
    let counter = 1;
    
    // loop until we find the kth missing positive number
    while (k > 0) {
        
        // if the current number isn't in the set, it's missing
        // so decrement k and return the number
        if (!nums.has(counter)) {
            k--;
            return counter;
        }
        
        // otherwise, increment the counter and continue
        counter++;
    }
};

class Solution {
public:
    int findKthPositive(vector& arr, int k) {
        int n = arr.size(); 
  
        // Initialize missing values 
        int missing_values = 0; 
  
        // Traverse the array from left 
        for (int i = 0; i < n; i++) { 
            // Check if arr[i] - 1 is present in 
            // the array or not 
            if (i != arr[i] - 1) { 
                // If not present then increment 
                // missing_values 
                missing_values++; 
            } 
  
            // If missing_values becomes equal to 
            // k then return i + 1 
            if (missing_values == k) 
                return i + 1; 
        } 
  
        // If kth missing element is not present 
        // in the array 
        return n + k; 
    } 
};

public int FindKthPositive(int[] arr, int k) { // create a hashset to store all positive integers in the array HashSet positiveInts = new HashSet(); foreach(int num in arr) { if(num > 0) { positiveInts.Add(num); } } // iterate through all positive integers, // starting from 1 int counter = 1; while(k > 0) { // if the current integer is not in the hashset, // it is the kth missing positive integer if(!positiveInts.Contains(counter)) { k--; } // move on to the next positive integer counter++; } // counter will be at the kth missing positive integer when the loop exits return counter - 1; }