CareerCup

Question lacks clarity.Should have more inputs to find k.

O(n) solution with O(n) memory:

Input array: A of length n

1. Find min value of the input, lets call it X. O(n)

2. if X!=Integer.MIN then output=Integer.MIN (corner case)

3. Create a boolean array of length n with default value FALSE. Lets call it P.

4. The idea is to check if the input array contains numbers from X to X+(n-1) using n sized boolean array. Then output is any element that is missing from the range X to X+(n-1) and if none are missing then the output is X+n, unless X+n=Integer.MAX in which case the input array contains all possible integers from Integer.MIN to Integer.MAX.

for(i = 0 to n-1) {
	j=A[i]-X
	if(j<n) then P[j]=TRUE
}

for(i=0 to n-1) {
	if P[i]==FALSE then output is Integer.MIN+i
}

if i==n && n!=(Integer.MAX+1-Integer.MIN) then output is Integer.MIN+n
else "no output"// corner case of input array containing all integers

--- O(n)

e.g
Input A = {1,-1,Integer.MIN,2,3,5}
X = Integer.MIN
P = {TRUE,FALSE,FALSE,FALSE,FALSE,FALSE}
Output = Integer.MIN+1

I think may be the questions is, "Find the missing number in a continuous integers"

-> Find the sum of integers.
-> Sum the array.
-> Take the difference gives the exact number