Usually my youngest son calls on his way to work. Is almost 10:00 AM and have not heard from him. I work from home so I am able to receive his calls pretty much any time. I do not like to call him because he works out in the mornings and has to go home, get ready and drive to work. His time varies from day to day. We have this unspoken arrangement that if he does not have a chance to call we will do so the next day.
The arrangement is exactly the opposite on weekends. I tend to call him as soon as my wife and I head out for the first activity of the day. Typically is on our way to or from shopping for groceries or running any other morning errand.
As I was typing my son called. It seems like Madison, WI received some snow 
last night. There is about an inch of wet stuff on trees and lawns. The roads and driveways appear to be clean. We chatted for a few minutes and he arrived at his office.
I tackled problem 17.19 in the Cracking the Coding Interview book by Gayle Laakmann McDowell. Seems like a more stringent version of the Missing Number problem which I visited in a previous post.
The text for the problem follows:
“You are given an array with all the numbers from 1 to N appearing exactly once, except for one number that is missing. How can you find the missing number in O(N) time and O(1) space? What if there were two numbers missing?”
I strongly recommend getting a copy of the book if you are interested in solving problems. There are so many problems in the book that should keep you busy for a few years.
Now that we have the requirement statement I will show my tinkering on the white board.
I decided to go for the gold. The first part of the function addresses finding the first missing number. The second takes care of the second missing value. The idea is that we keep the monotonically ascending integers starting with one (1) in an array. This will become clearer while we visit the Java code written using the Visual Studio Code IDE.
(base) PS C:\Users\John\workspace6\MissingTwo> & 'C:\Users\John\.vscode\extensions\vscjava.vscode-java-debug-0.23.0\scripts\launcher.bat' 'C:\ProgramData\Oracle\Java\jdk1.8.0_221\bin\java' '-Dfile.encoding=UTF-8' '-cp' 'C:\Users\John\workspace6\MissingTwo\bin' 'Solution' main <<< size: 12 main <<< count: 1 populateArray <<< f: 10 main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13] length: 12 main <<< missing: 10 (base) PS C:\Users\John\workspace6\MissingTwo> cd 'c:\Users\John\workspace6\MissingTwo'; & 'C:\Users\John\.vscode\extensions\vscjava.vscode-java-debug-0.23.0\scripts\launcher.bat' 'C:\ProgramData\Oracle\Java\jdk1.8.0_221\bin\java' '-Dfile.encoding=UTF-8' '-cp' 'C:\Users\John\workspace6\MissingTwo\bin' 'Solution' main <<< size: 13 main <<< count: 2 main <<< consecutive: true populateArray <<< f: 11 s: 12 main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15] length: 13 main <<< missing: 11, 12 (base) PS C:\Users\John\workspace6\MissingTwo> cd 'c:\Users\John\workspace6\MissingTwo'; & 'C:\Users\John\.vscode\extensions\vscjava.vscode-java-debug-0.23.0\scripts\launcher.bat' 'C:\ProgramData\Oracle\Java\jdk1.8.0_221\bin\java' '-Dfile.encoding=UTF-8' '-cp' 'C:\Users\John\workspace6\MissingTwo\bin' 'Solution' main <<< size: 13 main <<< count: 2 main <<< consecutive: false populateArray <<< f: 8 s: 12 main <<< arr: [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15] length: 13 main <<< missing: 8, 12 (base) PS C:\Users\John\workspace6\MissingTwo> cd 'c:\Users\John\workspace6\MissingTwo'; & 'C:\Users\John\.vscode\extensions\vscjava.vscode-java-debug-0.23.0\scripts\launcher.bat' 'C:\ProgramData\Oracle\Java\jdk1.8.0_221\bin\java' '-Dfile.encoding=UTF-8' '-cp' 'C:\Users\John\workspace6\MissingTwo\bin' 'Solution' main <<< size: 22 main <<< count: 2 main <<< consecutive: false populateArray <<< f: 4 s: 17 main <<< arr: [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23, 24] length: 22 main <<< missing: 4, 17 (base) PS C:\Users\John\workspace6\MissingTwo> cd 'c:\Users\John\workspace6\MissingTwo'; & 'C:\Users\John\.vscode\extensions\vscjava.vscode-java-debug-0.23.0\scripts\launcher.bat' 'C:\ProgramData\Oracle\Java\jdk1.8.0_221\bin\java' '-Dfile.encoding=UTF-8' '-cp' 'C:\Users\John\workspace6\MissingTwo\bin' 'Solution' main <<< size: 15 main <<< count: 2 main <<< consecutive: true populateArray <<< f: 7 s: 8 main <<< arr: [1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15, 16, 17] length: 15 main <<< missing: 7, 8 (base) PS C:\Users\John\workspace6\MissingTwo>
I ran the program a few times by pressing Control+F5 while focused on the IDE.
The program displays the size of the integer array selected for this pass. In the first example the software chose an array with 12 elements. The count of missing numbers was selected to be 1. Number 10 will be missing from the array. The array is then displayed. We are able to verify that the array contains 12 elements, it starts with number 1 and number 10 is missing. After the missingNumbers() method is invoked we display the missing number which happens to match the one that was omitted.
On the third run, the program chose an array with 13 elements. It also chose to have two missing numbers. The missing numbers are not consecutive. The selected missing numbers are 8 and 12. The array is built and we can verify that both numbers are missing. The missingNumbers() method returns the missing numbers which match the ones that were omitted from the array.
Finally let’s look at the output of the last run. Note that the program chose to remove two consecutive numbers. In this case it chose 7 and 8. The contents of the array show that the selected numbers have been omitted. The missingNumbers() method appears to have selected the proper missing numbers.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** ****
final int MAX_ARRAY_LENGTH = 23;
final int MIN_ARRAY_LENGTH = 5;
// **** determine the array size ****
int size = MIN_ARRAY_LENGTH + rand.nextInt(MAX_ARRAY_LENGTH - MIN_ARRAY_LENGTH);
// ???? ????
System.out.println("main <<< size: " + size);
// ***** determine number of missing values ****
int count = 1 + rand.nextInt(2);
// ???? ????
System.out.println("main <<< count: " + count);
// **** determine if missing value(s) are consecutive ****
boolean consecutive = rand.nextBoolean();
// ???? ????
if (count == 2)
System.out.println("main <<< consecutive: " + consecutive);
// **** populate the array ****
int[] arr = populateArray(size, count, consecutive);
// ???? ????
System.out.print("main <<< arr: [");
for (int i = 0; i < arr.length; i++) {
if (i + 1 < arr.length)
System.out.print(arr[i] + ", ");
else
System.out.print(arr[i]);
}
System.out.println("] length: " + arr.length);
// **** find missing values ****
int[] missing = missingNumbers(arr);
// **** display missing number(s) ****
System.out.print("main <<< missing: " + missing[0]); if (missing[1] >= 1)
System.out.println(", " + missing[1]);
System.out.println();
}
For simplicity I selected a minimum and a maximum size for the integer array to be populated and tested. A pseudo random number generator is used to define the size of the array, the count of missing values, and decide if the two missing numbers are consecutive or not. I thought it would be a good idea to test the solution against both cases. As I have mentioned multiple 
times in this post, I use the Test Driven development (TDD) approach when designing and implementing software. Please note that I use the essence behind TDD and not the mechanical parts which only reflect one of the procedures one can take to use the technique. In production one the software seems to be working well (in this case it will be now), I would think of the unit tests that would make sense to have and would implement them using once again a TDD approach. This implies coming up with an initial set of unit tests and while implementing them, new ones may be added, some might not be implemented, and most important the actual software might change due to the unit testing. PLEASE NOTE THAT THE ESSENCE OF TDD DOES NOT REQUIRE THE USE OF A SPECIFIC TOOL OR FRAMEWORK TO WRITE TESTS. In our case I have used our main() method for testing while designing and implementing.
// **** to add variety to the test ****
static Random rand = new Random();
/*
* Instantiate and populate the array.
* Array start with number 1.
*/
static int[] populateArray(int size, int count, boolean consecutive) {
// **** ****
int[] arr = new int[size];
// **** determine first missing number ****
int f = 1 + rand.nextInt(size - 2);
int s = Integer.MAX_VALUE;
// **** determine the second missing number (if needed) ****
if (count == 2) {
if (consecutive)
s = f + 1;
else {
s = (f + 1) + rand.nextInt(size - f - 1);
}
}
// ???? ????
System.out.print("populateArray <<< f: " + f);
if (count == 2)
System.out.print(" s: " + s);
System.out.println();
// **** populate the array ****
int val = 1;
for (int i = 0; i < arr.length; i++, val++) {
// **** ****
if (val == f) {
val++;
if (val == s)
val++;
arr[i] = val;
continue;
}
// **** ****
if (val == s) {
val++;
arr[i] = val;
continue;
}
// **** ****
arr[i] = val;
}
// **** return array with missing numbers(s) ****
return arr;
}
The populateArray() method is used to create the integer array using the specified size. Once that has been taken care of, the method randomly selects the first missing number. We could have selected the second one and not using it. I decided to follow the thought pattern instead. Another reason for not choosing it yet is to check if the missing numbers are consecutive or not.
Now we are ready to start populating the array. The loop illustrates how this is done. I assume each developer would come up with a different approach. For example, build a list with enough length and all the numbers. Delete the number or two numbers. Convert the list to an array. I just wanted to complete the algorithm as it was started. In practice the second approach might be simpler to visualize and maintain.
/*
* Find one or two missing number(s) in the specified array.
*/
static int[] missingNumbers(int[] arr) {
// **** array holding one or two missing number(s) ****
int[] missing = {-1, -1};
int f = -1;
int s = -1;
// **** traverse array (only once) ****
for (int i = 0; i < arr.length; i++) {
// **** check for first missing number (if needed) ****
if (f == -1) {
if ((i + 1) != arr[i]) {
f = i + 1;
}
}
// **** check for second missing number (if needed) ****
if ((f != -1) && (s == -1)) {
if ((i + 2) != arr[i]) {
s = i + 2;
break;
}
}
}
// **** populate the missing number(s) ****
missing[0] = f;
missing[1] = s;
// **** ****
return missing;
}
The missingNumbers() method returns an array of two elements. The first element will always hold the first missing number. The second element may or may not hold a second number. If the method does not find a second missing value then the second element in the array returns a minus one (-1).
We traverse the array starting from the first element and stop after both missing numbers are found. If the array only contains a single missing value, then the loop traverses all the N entries.
The check for the first missing number determines if the value in the array 
differs from the index by one. The second check is similar but it checks if the value differs by two. Since we do not have a third missing value, we can break out of the loop. If we do not, we still run at O(N) time.
When I was done I did check the solution form the book. It seems to me that unless I have missed something in the requirements, my solution is simpler and more elegant. I will post a message on the website for the book. Will let you know if and when I receive a reply.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa