It is Friday, April 17, 2020 and the COVID-19 pandemic is still around. It seems like China is responsible for this pandemic that has affected the entire world. It is a shame that China put the lives of thousands in front of their reputation and ambitions. Hopefully the world will stop manufacturing products in China. Remember that China copies and steals all product and manufacturing technologies they collect from foreign companies manufacturing there.
Let’s get into the main subject for this post. A few months I posted Missing Numbers. The proposed solution looked at all bits in all the numbers. Based 
on the text of the requirements I asked the “virtual interviewer” if the array was sorted in monotonically ascending order. The “virtual interviewer” said they were so I came with the solution illustrated in the previous post.
By the way, there was no “virtual interviewer”. I read the requirements and as far I recall there was no mention if the numbers were out of order. Of course I was not sure if that was correct so I sent a message to the book author requesting clarification. I received a response about a week ago. Her response follows:
Hi John, Just getting to these --- The issue with your proposal is that it assumes that the items in the list are in order. If this were the case, then your solution would work. However, you can't make that assumption for this problem. Thanks! Gayle
Well, you can always try.
I decided to take the original code, edited as needed, and add a second approach that would consider the numbers in the array not in order.
# **** **** Microsoft Windows [Version 10.0.18363.778] (c) 2019 Microsoft Corporation. All rights reserved. # **** **** C:\Users\johnc>dir 04/08/2020 07:59 AM <DIR> . 04/08/2020 07:59 AM <DIR> .. 09/22/2019 08:00 AM <DIR> .eclipse 03/15/2020 08:38 AM 59 .gitconfig 04/07/2020 10:38 AM <DIR> .p2 09/22/2019 08:00 AM <DIR> .tooling 03/10/2020 03:53 PM <DIR> .vscode 03/10/2020 04:43 PM <DIR> 3D Objects 03/10/2020 04:43 PM <DIR> Contacts 04/08/2020 07:59 AM <DIR> ContainsCloseNums 02/17/2020 03:52 PM <DIR> Documents 04/03/2020 03:20 PM <DIR> Downloads 09/22/2019 07:57 AM <DIR> eclipse 09/22/2019 07:59 AM <DIR> eclipse-workspace_0 03/10/2020 04:43 PM <DIR> Favorites 03/10/2020 04:44 PM <DIR> Links 03/10/2020 04:43 PM <DIR> Music 09/12/2019 04:36 PM <DIR> NCH Software Suite 04/15/2020 08:15 AM <DIR> OneDrive 03/10/2020 04:43 PM <DIR> Saved Games 03/10/2020 04:43 PM <DIR> Searches 03/10/2020 04:43 PM <DIR> Videos 04/10/2020 11:29 AM <DIR> workspace0 # **** **** C:\Users\johnc>cd workspace0 # **** **** C:\Users\johnc\workspace0>dir 04/10/2020 11:29 AM <DIR> . 04/10/2020 11:29 AM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/10/2020 11:34 AM <DIR> ComposeRanges 04/08/2020 08:04 AM <DIR> ContainsCloseNums 04/05/2020 08:32 AM <DIR> GraphBFS 03/29/2020 08:30 AM <DIR> ORCost 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** **** C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/MissingNumber.git Cloning into 'MissingNumber'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), 1.50 KiB | 30.00 KiB/s, done. # **** **** C:\Users\johnc\workspace0>dir 04/15/2020 01:45 PM <DIR> . 04/15/2020 01:45 PM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/10/2020 11:34 AM <DIR> ComposeRanges 04/08/2020 08:04 AM <DIR> ContainsCloseNums 04/05/2020 08:32 AM <DIR> GraphBFS 04/15/2020 01:45 PM <DIR> MissingNumber 03/29/2020 08:30 AM <DIR> ORCost 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** **** C:\Users\johnc\workspace0>cd MissingNumber # **** seems like we are missing a README.md file (will add one when done) **** C:\Users\johnc\workspace0\MissingNumber>dir 04/15/2020 01:45 PM <DIR> . 04/15/2020 01:45 PM <DIR> .. 04/15/2020 01:45 PM 2,612 Solution.java
I am using multiple computers and for a few months have been using git from a console to access GitHub. The last line of the screen capture illustrates that I did not include a README.md file. Will add a simple one before we update the solution.
main <<< n: 12 main <<< m: 8 main <<< arr: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12] main <<< missing: 8 == m: 8 main <<< arr: [9, 5, 12, 0, 11, 4, 7, 1, 3, 10, 2, 6] main <<< missing: 8 == m: 8 main <<< n: 4 main <<< m: 2 main <<< arr: [0, 1, 3, 4] main <<< missing: 2 == m: 2 main <<< arr: [0, 3, 4, 1] main <<< missing: 2 == m: 2 main <<< n: 19 main <<< m: 17 main <<< arr: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19] main <<< missing: 17 == m: 17 main <<< arr: [18, 10, 13, 11, 14, 16, 7, 4, 6, 9, 8, 19, 2, 0, 1, 12, 5, 3, 15] main <<< missing: 17 == m: 17 main <<< n: 14 main <<< m: 0 main <<< arr: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] main <<< missing: 0 == m: 0 main <<< arr: [5, 6, 1, 13, 9, 11, 8, 12, 4, 2, 14, 7, 10, 3] main <<< missing: 0 == m: 0
The output displays a couple numbers. The first is the number of elements in the array. The second is the missing number. The array in monotonically ascending order is displayed. We can verify the count of numbers and the missing value.
We run the method that solves the problem if the numbers are in ascending order. The solution seems to work.
We then display an array with the values shuffled. If we try (which is not illustrated here) to run the shuffled array through the first method, the missing number is not found. We use a new method that takes a shuffled (or random array) and the missing number is found.
/**
* Test scaffolding.
* random.nextInt(max - min + 1) + min
*/
public static void main(String[] args) {
// **** ****
final int MAX_LENGTH = 19;
final int MIN_LENGTH = 2;
// **** ****
Random rand = new Random(System.currentTimeMillis());
// **** determine n ****
int n = Math.abs(rand.nextInt(MAX_LENGTH - MIN_LENGTH + 1)) + MIN_LENGTH;
// ???? ????
System.out.println("main <<< n: " + n);
// **** determine the missing value ****
int m = Math.abs(rand.nextInt((n - 1) - 0 + 1) + 0);
// ???? ????
System.out.println("main <<< m: " + m);
// **** declare array list ****
ArrayList<Integer> al = new ArrayList<Integer>();
// **** populate array list with a missing number ****
int j = 0;
for (int i = 0; i < n; i++) {
// **** skip this value ****
if (i == m)
j++;
// **** populate array with this value ****
al.add(j++);
}
// **** populate array with the contents of the array list ****
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = al.get(i);
// ???? ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** missing number ****
int missing;
// **** find the missing number ****
missing = findMissingSorted(arr);
// **** check if we found the proper missing number ****
if (missing == m)
System.out.println("main <<< missing: " + missing + " == m: " + m);
else
System.err.println("main <<< missing: " + missing + " != m: " + m + " :o(");
// **** shuffle the array list ****
Collections.shuffle(al);
// **** populate array with the contents of the array list ****
arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = al.get(i);
// ???? display the shuffled array ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** find the missing number ****
missing = findMissing(arr);
// **** check if we found the proper missing number ****
if (missing == m)
System.out.println("main <<< missing: " + missing + " == m: " + m);
else
System.err.println("main <<< missing: " + missing + " != m: " + m + " :o(");
}
The code as before is written in Java. Last time around I was using the Eclipse IDE. This time I used VSCode.
We declare a couple constants to limit the numbers in the array. While testing I increased the upper boundary.
We use a random number generator to determine the size of the array. We then randomly determine the value for the missing number.
We use an ArrayList and populate it with the values as specified by the random values n and m. An array is declared and the values from the array list are copied into it. The array is displayed.
We then call the findMissingSorted method (this is the original solution) and display the returned value.
For the new section of the code, we shuffle the contents in the array list. We do so to use the same set of initial values. The array is populated and displayed.
Now we call the findMissing method and display the result.
/**
* Find missing value in O(n).
* arr[i] & 0x01 is equivalent to fetch the 0th bit (LSB) from arr[i].
*/
static int findMissingSorted(int[] arr) {
// **** ****
int missing = 0;
// **** traverse array looking for missing value ****
for (int i = 0; i < arr.length; i++) {
if ((i % 2) != fetchBit(arr, i, 0)) {
missing = i;
break;
}
}
// **** ****
return missing;
}
This is the method that only works with a sorted array. Not much (if any) has changed from the original post.
/**
* Fetch jth bit from arr[i]
*/
static int fetchBit(int[] arr, int i, int j) {
// **** (we should really throw an exception) ****
if (i >= arr.length)
return 0;
// **** (we should really throw an exception) ****
if ((j < 0) || (j >= 32))
return 0;
// **** mask for jth bit ***
int mask = 1;
for (int k = 0; k < j; k++)
mask <<= 1;
// **** return the requested bit value ****
return arr[i] & mask;
}
This auxiliary method has not changed from the last post. It provides a way to get to a single bit at a time in the array. In our new solution we will use a simpler and in-line approach.
/**
* Converts array to array list.
* Start recursion.
*/
static int findMissing(int[] arr) {
// **** ****
ArrayList<Integer> al = new ArrayList<Integer>();;
// **** populate array list ****
for (int i = 0; i < arr.length; i++)
al.add(arr[i]);
// **** start recursion with LSB ****
return findMissing(al, 0);
}
This is the entry point for the new approach. I just wanted to keep the integer array argument. We could just have called from main the next recursive method.
/**
* Recursive call.
*/
static int findMissing(ArrayList<Integer> al, int lsb) {
// **** end / stop condition ****
if (lsb >= Integer.SIZE)
return 0;
// **** ****
ArrayList<Integer> oneBits = new ArrayList<Integer>();
ArrayList<Integer> zeroBits = new ArrayList<Integer>();
// **** set mask ****
int mask = 1;
mask <<= lsb;
// **** populate array lists ****
for (Integer i : al) {
if ((i & mask) == 0) {
zeroBits.add(i);
} else {
oneBits.add(i);
}
}
// **** recursive call ****
if (zeroBits.size() <= oneBits.size()) {
int v = findMissing(zeroBits, lsb + 1);
return (v << 1);
} else {
int v = findMissing(oneBits, lsb + 1);
return (v << 1) | 1;
}
}
This is a recursive call. The approach is to count the number of 0s and 1s in the less significant bit and put them in two different array lists for further processing. One array list will contain all the numbers that have a LSB (less significant bit) of 0 and the other all the numbers with LSB of 1.
For the separation of values we will use a mask. The mask if initialized to 1 and shifted left as specified by the argument lsb. This allows us to select the proper column of bits from the numbers without modifying them or adding a utility method like we did in the previous approach.
Now we make one of two recursive calls. One used the zeroBits array list while the other the oneBits array list. The returned values are shifted in order to allow us to rebuild the missing number.
But how do we decide on which recursive call to make? The answer is to observe the count of numbers we have ending with a 0 or a 1. You can get write a few binary values and follow a simple example. The key is to note how the counts of 0s and 1s relate to each other. Once you experiment with a few examples it becomes clear. If the count of 0s is less than or equal to the count of 1s, we select the zeroBits array list; otherwise we select the oneBits array 
list.
The book has two different explanations. If you are interested in solving this problem on your own I strongly recommend to get a copy of “Cracking the Coding Interview” by Gayle Laakmann McDowell. I currently own the 6th edition of the book. I had a previous edition but apparently it grew legs and walk away.
Note that my solution does not make use of the BitInteger class illustrated in the book. If I recall right, at some point in the book a set of classes and methods are created to help solving problems. I know a read and experimented with them last year. I did not find and index in the book to lead me to the section containing such class. It seems that just using an Integer was quite simple and with less dependencies to use.
# **** ****
Microsoft Windows [Version 10.0.18363.778]
(c) 2019 Microsoft Corporation. All rights reserved.
# **** ****
C:\Users\johnc>dir
04/16/2020 02:31 PM <DIR> .
04/16/2020 02:31 PM <DIR> ..
09/22/2019 08:00 AM <DIR> .eclipse
03/15/2020 08:38 AM 59 .gitconfig
04/07/2020 10:38 AM <DIR> .p2
04/16/2020 02:31 PM <DIR> .pylint.d
09/22/2019 08:00 AM <DIR> .tooling
03/10/2020 03:53 PM <DIR> .vscode
03/10/2020 04:43 PM <DIR> 3D Objects
03/10/2020 04:43 PM <DIR> Contacts
04/08/2020 07:59 AM <DIR> ContainsCloseNums
02/17/2020 03:52 PM <DIR> Documents
04/17/2020 09:22 AM <DIR> Downloads
09/22/2019 07:57 AM <DIR> eclipse
09/22/2019 07:59 AM <DIR> eclipse-workspace_0
03/10/2020 04:43 PM <DIR> Favorites
03/10/2020 04:44 PM <DIR> Links
03/10/2020 04:43 PM <DIR> Music
09/12/2019 04:36 PM <DIR> NCH Software Suite
04/17/2020 06:53 AM <DIR> OneDrive
03/10/2020 04:43 PM <DIR> Saved Games
03/10/2020 04:43 PM <DIR> Searches
03/10/2020 04:43 PM <DIR> Videos
04/15/2020 01:45 PM <DIR> workspace0
# **** ****
C:\Users\johnc>cd workspace0
# **** ****
C:\Users\johnc\workspace0>dir
04/15/2020 01:45 PM <DIR> .
04/15/2020 01:45 PM <DIR> ..
04/01/2020 08:57 AM <DIR> BST-Search
04/10/2020 11:34 AM <DIR> ComposeRanges
04/08/2020 08:04 AM <DIR> ContainsCloseNums
04/05/2020 08:32 AM <DIR> GraphBFS
04/17/2020 03:41 PM <DIR> MissingNumber
03/29/2020 08:30 AM <DIR> ORCost
03/10/2020 04:24 PM <DIR> SortOnFrequency
# **** ****
C:\Users\johnc\workspace0>cd MissingNumber
# **** check we are using the proper remote GitHub repository ****
C:\Users\johnc\workspace0\MissingNumber>git remote -v
origin https://github.com/JohnCanessa/MissingNumber.git (fetch)
origin https://github.com/JohnCanessa/MissingNumber.git (push)
# **** ****
C:\Users\johnc\workspace0\MissingNumber>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git restore <file>..." to discard changes in working directory)
modified: Solution.java
Untracked files:
(use "git add <file>..." to include in what will be committed)
README.md
no changes added to commit (use "git add" and/or "git commit -a")
# **** add the updated Solution.java file ****
C:\Users\johnc\workspace0\MissingNumber>git add Solution.java
# **** add the newly created README.md file ****
C:\Users\johnc\workspace0\MissingNumber>git add README.md
# **** ****
C:\Users\johnc\workspace0\MissingNumber>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git restore --staged <file>..." to unstage)
new file: README.md
modified: Solution.java
# **** ****
C:\Users\johnc\workspace0\MissingNumber>git commit -m "new approach using shuffled array"
[master c2cea9d] new approach using shuffled array
2 files changed, 130 insertions(+), 30 deletions(-)
create mode 100644 README.md
# **** ****
C:\Users\johnc\workspace0\MissingNumber>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
# **** ****
C:\Users\johnc\workspace0\MissingNumber>git push origin master
Enumerating objects: 6, done.
Counting objects: 100% (6/6), done.
Delta compression using up to 12 threads
Compressing objects: 100% (4/4), done.
Writing objects: 100% (4/4), 1.38 KiB | 1.38 MiB/s, done.
Total 4 (delta 1), reused 0 (delta 0)
remote: Resolving deltas: 100% (1/1), completed with 1 local object.
To https://github.com/JohnCanessa/MissingNumber.git
16931fe..c2cea9d master -> master
# **** ****
C:\Users\johnc\workspace0\MissingNumber>git status
On branch master
Your branch is up to date with 'origin/master'.
nothing to commit, working tree clean
# **** ****
C:\Users\johnc\workspace0\MissingNumber>git log
commit c2cea9df9d23a670d95d2ea2e8ea34545b9a5d22 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Fri Apr 17 15:48:01 2020 -0500
new approach using shuffled array
commit 16931fe76b1ddce18ea89676f96cd3102f32b588
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Fri Oct 18 10:06:17 2019 -0500
Add files via upload
After making sure all is well, I added the edited Solution.java and the newly created README.md files. The files were committed and pushed to GitHub. The git log shows the expected history.
I will go back and edit the README.md file as soon as I generate and post with this text on my WordPress blog and update the link that points to it.
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 for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
I want to thanks Gayle for the response to my message. By the way I am not associated in any way with the author, publishers or sellers of the Cracking the Coding Interview book.
One last thing, thanks to all 615 subscribers to my blog!!!
John
Twitter: @john_canessa