FastPrepFastPrep
Problem Brief

Kth Missing Positive Number (for E4 :)

FULLTIMEPHONE SCREEN

LC 1539~ The other question was LC 498~~

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

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

Function Description

Complete the function findKthPositive in the editor.

findKthPositive has the following parameters:

  1. 1. int[] arr: an array of integers
  2. 2. int k: an integer

Returns

int: the kth missing positive integer

Constraints

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

Follow up

Could you solve this problem in less than O(n) complexity?

1Example 1

Input
arr = [2,3,4,7,11], k = 5
Output
9
Explanation

The missing positive integers are [1,5,6,8,9,10,12,...]. The 5th missing positive integer is 9.

2Example 2

Input
arr = [1,2,3,4], k = 2
Output
6
Explanation

The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6. 

public int findKthPositive(int[] arr, int k) {
  // write your code here
}
Input

arr

[2,3,4,7,11]

k

5

Output

9

Sign in to submit your solution.