I just got off the phone with my youngest son. He was on his way to work. He calls every workday and I call him every weekend. It has become some type of tradition. Today the weather in the Twin Cities of Minneapolis and St. Paul is sunny and cold with the temperature at 11 F. In Madison, WI it is a few degrees warmer.
Yesterday we did not talk. My son called but apparently my Pixel phone did 
not pick up the call. The phone did not register a missed call. During the day I received and made calls. I lost my phone a couple weeks ago. I replaced it with a Pixel 4 XL. Currently my other son and my wife also have Pixel phones. My son changed his carrier to Fi, a service offered by Google. My wife and I remain with T-Mobile. She has mentioned a couple occasions in which people had tried getting a hold of her and the phone missed the call(s) and did not make an entry in the missed calls log. I should search the internet for issues with the Pixel phone missing calls.
My wife needed some help with her computer. A pop-up would show up when she would start the Chrome web browser on her Windows 10 laptop. The pop-up indicated some conflict with the Edge web browser. She has never used 
Edge. My first reaction was to reinstall Chrome. I uninstalled chrome and restarted the laptop. When it came up I installed Chrome. I then restarted the laptop. I waited for it to come up. My wife was able to log on to Gmail.
OK, I missed a few minutes from my 2-hour block. I reset EyeDefender on my computer. We will have lunch at 01:00 PM instead of the usual 12:00 PM.
I received a message from HackerRank to attempt to solve the challenge Sansa and XOR. The challenge is ranked with difficulty of medium, but it took more time than expected. The reason is that you have to figure out a pattern and then work out the code to implement it. In addition I had a typo (will mention it when we visit the actual Java code) which passed all the sample test cases but failed all the test cases when I submitted the code.
1 3 3 4 5 6 1 4 4 5 7 5 0 1 7 1 2 3 4 5 6 7 2 1 2 7 11 0 2 3 1 2 3 4 4 5 7 5 2 0 2 3 98 74 12 3 50 13 2 110 48 1 7 1111111 22222222 333333333 444444444 555555555 6666666 777777777 478699392
I wrote the solution using Java 8 and the Visual Studio Code IDE.
The test cases mostly came from the HackerRank challenge web page. I spent time looking at the description of the problem and looking for patterns that I could identify and then make sense out of them.
// **** open the scanner ****
private static final Scanner scanner = new Scanner(System.in);
/**
* Test scaffolding.
*/
public static void main(String[] args) throws IOException {
// **** buffered writer to system.out****
// BufferedWriter bufferedWriter = new BufferedWriter(new
// FileWriter(System.getenv("OUTPUT_PATH")));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
// **** number of test cases ****
int t = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// **** loop once per test case ****
for (int tItr = 0; tItr < t; tItr++) {
// **** ****
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// **** instantiate the array of integers ****
int[] arr = new int[n];
// **** read all the integer values ****
String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
// **** load the array of integers ****
for (int i = 0; i < n; i++) {
int arrItem = Integer.parseInt(arrItems[i]);
arr[i] = arrItem;
}
// **** compute result ****
int result = sansaXor(arr);
// **** display result ****
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
// **** close the buffered writter ****
bufferedWriter.close();
// **** close the scanner ****
scanner.close();
}
The test scaffolding follows the usual pattern. I added comments and changed the instantiation of the buffered writer.
We read the number of test cases, and then loop once per test case. Each test case contains the number of integers followed in the next line by the actual values. The values are inserted into an array of the proper size and the sansaXor() method is called. The result is displayed.
When all is set and done we closed the buffered writer and the scanner.
/**
* 1. When the number of values is EVEN, the resulting subarrays are:
*
* Sample case: {1, 2 ,3, 4}
*
* 1⊕2⊕3⊕4⊕(1⊕2)⊕(2⊕3)⊕(3⊕4)⊕(1⊕2⊕3)⊕(2⊕3⊕4)⊕(1⊕2⊕3⊕4)
*
* Notice that 1 occurs an EVEN number of times, so as for 2, 3, and 4. XORing
* any number an EVEN number of times results in 0.
*
* 2. When the number of values is ODD, the resulting subarrays are:
*
* Sample case: {1, 2, 3, 4, 5}
*
* 1⊕2⊕3⊕4⊕5⊕(1⊕2)⊕(2⊕3)⊕(3⊕4)⊕(4⊕5)⊕(1⊕2⊕3)⊕(2⊕3⊕4)⊕(3⊕4⊕5)⊕(1⊕2⊕3⊕4)⊕(2⊕3⊕4⊕5)⊕(1⊕2⊕3⊕4⊕5)
*
* Notice that every EVEN index (0, 2, 4, ...) occurs an ODD number of times and
* every ODD index (1, 3, 5, ...) occurs an EVEN number of times.
*/
static int sansaXor(int[] arr) {
// **** for starters ****
int sum = 0;
// **** get the number of elements in the array ****
int n = arr.length;
// **** process array when n is ODD ****
if ((n % 2) == 1) {
// **** initilaize sum (i == 0) ****
sum = arr[0];
// **** loop through all EVEN indices in arr (i: [2, 4, 6, ...]) ****
for (int i = 2; i < n; i += 2) {
sum ^= arr[i];
}
}
// **** return sum ****
return sum;
}
I mentioned that I had a bug in the code. My bug was very simple. The comment over the loop indicates all even values. I incorrectly set the increment to i++ instead of i += 2 which was incorrect and did not match the comment.
The key to solve this and probably most pattern problems is to start with a brute force approach and look for patterns which can simplify the code. In this case from a O(n^3) down to an O(n) time complexity. I wrote the two patterns that needed to be observed in the comment section of the function.
The first pattern is somewhat easy to detect, understand and code. If the number of integers in the array is EVEN then the result is 0. Let’s figure this out using an example.
| Step | Operation | Note |
| 1 | 0101 | First instance for an integer (5) in the sequence of XOR operations. N/A |
| 2 | 0101 ^ 0101 = 0000 | Occurrence number 2 (even). Contribution results in 0. |
| 3 | 0000 ^ 0101 = 0101 | N/A |
| 4 | 0101 ^ 0101 = 0000 | Occurrence number 4 (even). Contribution results in 0. |
| 5 | 0000 ^ 0101 = 0101 | N/A |
| 6 | 0101 ^ 0101 = 0000 | Occurrence number 6 (even). Contribution results in 0. |
The second pattern conveniently shows up when the number of entries is ODD. In that case we need to generate the sum by looping through all the ODD array entries and XOR them with running value of the sum.
Once all is said and done, the code is simple and elegant. Finding the pattern took 90% of the time, writing the code the remaining 10%.
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!
John
Twitter: @john_canessa