Model N Interview Question
Applications DevelopersCountry: United States
Interview Type: Phone Interview
N should be the maximum positive number in the array not the number of elements in the array.
also... if N*(N+1)/2 == S, then the number is N+1;
for example.. in the array, 3, 4, 2, 1, the answer is 5...
numbs = [1,2,4,5,-1,0]
min = numbs[0]
max = numbs[0]
missing = -1
for n in numbs[1:]:
if (n <= 0):
continue
if (n < min):
if(n+1 < min):
missing = n+1
else:
min = n
if (n > max and missing == -1):
if(max+1 < n):
missing = max+1
max = n
if missing == -1:
missing = max+1
print missing
Of course this will only work if only one number is missing from the sequence.
This solution works for any sequence not just the ones provided
(utilizes N*(N+1)/2)
public class Main {
public static void main(String[] args) {
int[] unsorted = { 15,17,18,20,13,21,19,14 };
findMissing(unsorted);
}
static void findMissing(int[] intArray) {
//can be any numbeer in the array
int smallestNumber = intArray[0];
int largestNumber = smallestNumber;
int arrayAddition = 0;
for (int eachNumber : intArray) {
arrayAddition += eachNumber;
if (eachNumber < smallestNumber)//get the smallest number
smallestNumber = eachNumber;
else if(eachNumber > largestNumber)//get the largest number
largestNumber = eachNumber;
}
int ZeroToLargest = ((largestNumber) * (largestNumber + 1))/2;
int ZeroToSmallest = ((smallestNumber - 1) * (smallestNumber))/2;
System.out.println(ZeroToLargest - ZeroToSmallest - arrayAddition);
}
}
if i understand your question correctly. the logic should be something like this
- skp September 28, 20121. Add all +ve integers let it be S
2. Let N be the total number of elements in the array. Missing number should be
N*(N+1)/2 - S
It works with the sample inputs you provided