A or B

Over the weekend I watched the YouTube video “Dealing with Negative Comments | AMA #3 – Ask Me Anything with Lex Fridman”. I have watched a few of his videos. I do enjoy them to the point that I have subscribed to them. There is one in which Lex interviews Donald Knuth and other where he interviews Andrew Ng. Both videos are over an hour so I will watch them over the weekend.

If you are interested in getting information about Lex Fridman you can find it here or there.

I picked the challenge “A or B” from HackerRank after receiving an email message. I guess that if you solve a few of their problems they like you to continue visiting their site and solving additional challenges. I like to work on one or two a week. I believe it is the only way to learn and / or refresh material.

The requirements are well described in the HackerRank web site. We will develop a solution in Java 8 using the Microsoft Visual Studio Code IDE. On a side note, yesterday I read a very good post on Python interfaces so I will be adding Python support to VSCode in the next day or so. More on this in future posts.

I logged into GitHub and created the AorB repository. I also wrote a simple README.md file which will contain a link to this post. I have to add the link after the post it on WordPress.

# **** ****
C:\Users\John\workspace7>dir
02/29/2020  06:05 AM    <DIR>          .
02/29/2020  06:05 AM    <DIR>          ..
01/30/2020  01:32 PM    <DIR>          .metadata
01/31/2020  09:02 AM    <DIR>          .vscode
01/05/2020  07:15 AM    <DIR>          3DSurfaceArea
01/06/2020  11:52 AM    <DIR>          AlmostSorted
02/06/2020  07:16 AM    <DIR>          AndProduct
01/24/2020  12:49 PM    <DIR>          AStarSearch
12/05/2019  01:23 PM    <DIR>          BiggerIsGreater
02/25/2020  02:49 PM    <DIR>          BinaryTreeSum
02/14/2020  03:00 PM    <DIR>          Cipher
12/22/2019  08:35 AM    <DIR>          DeterminingDNAHealth
01/08/2020  07:07 AM    <DIR>          EmasSupercomputer
02/12/2020  02:46 PM    <DIR>          FirstDuplicate
02/03/2020  09:07 AM    <DIR>          FlippingBits
02/20/2020  08:14 AM    <DIR>          FullCountingSort
02/16/2020  09:09 AM    <DIR>          GitHubTest
01/31/2020  02:57 PM    <DIR>          guava-mini
01/31/2020  10:44 AM    <DIR>          HelloMaven
02/17/2020  10:43 AM         2,339,925 ij.jar
02/17/2020  10:52 AM    <DIR>          ImageJ
02/29/2020  06:05 AM    <DIR>          IsPermutation
02/22/2020  07:45 AM    <DIR>          JavaStreams
02/04/2020  02:04 PM    <DIR>          JumpingOnTheClouds
01/23/2020  08:05 AM    <DIR>          LarrysArray
12/03/2019  04:26 PM    <DIR>          MatrixLayerRotation
02/03/2020  10:42 AM    <DIR>          MiniMaxSum
01/25/2020  08:07 AM    <DIR>          PriorityQ
01/30/2020  01:42 PM    <DIR>          rtree2
02/03/2020  01:44 PM    <DIR>          SansaXOR
01/19/2020  09:16 AM    <DIR>          StacksReverseOrder
02/19/2020  08:08 AM    <DIR>          SumOfTwo
01/04/2020  07:51 AM    <DIR>          TheGridSearch
12/11/2019  10:09 AM    <DIR>          ToTrieOrNotToTrie

# **** ****
C:\Users\John\workspace7>git clone https://github.com/JohnCanessa/AorB.git
Cloning into 'AorB'...
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), done.

# **** ****
C:\Users\John\workspace7>dir
02/29/2020  09:10 AM    <DIR>          .
02/29/2020  09:10 AM    <DIR>          ..
01/30/2020  01:32 PM    <DIR>          .metadata
01/31/2020  09:02 AM    <DIR>          .vscode
01/05/2020  07:15 AM    <DIR>          3DSurfaceArea
01/06/2020  11:52 AM    <DIR>          AlmostSorted
02/06/2020  07:16 AM    <DIR>          AndProduct
02/29/2020  09:10 AM    <DIR>          AorB
01/24/2020  12:49 PM    <DIR>          AStarSearch
12/05/2019  01:23 PM    <DIR>          BiggerIsGreater
02/25/2020  02:49 PM    <DIR>          BinaryTreeSum
02/14/2020  03:00 PM    <DIR>          Cipher
12/22/2019  08:35 AM    <DIR>          DeterminingDNAHealth
01/08/2020  07:07 AM    <DIR>          EmasSupercomputer
02/12/2020  02:46 PM    <DIR>          FirstDuplicate
02/03/2020  09:07 AM    <DIR>          FlippingBits
02/20/2020  08:14 AM    <DIR>          FullCountingSort
02/16/2020  09:09 AM    <DIR>          GitHubTest
01/31/2020  02:57 PM    <DIR>          guava-mini
01/31/2020  10:44 AM    <DIR>          HelloMaven
02/17/2020  10:43 AM         2,339,925 ij.jar
02/17/2020  10:52 AM    <DIR>          ImageJ
02/29/2020  06:05 AM    <DIR>          IsPermutation
02/22/2020  07:45 AM    <DIR>          JavaStreams
02/04/2020  02:04 PM    <DIR>          JumpingOnTheClouds
01/23/2020  08:05 AM    <DIR>          LarrysArray
12/03/2019  04:26 PM    <DIR>          MatrixLayerRotation
02/03/2020  10:42 AM    <DIR>          MiniMaxSum
01/25/2020  08:07 AM    <DIR>          PriorityQ
01/30/2020  01:42 PM    <DIR>          rtree2
02/03/2020  01:44 PM    <DIR>          SansaXOR
01/19/2020  09:16 AM    <DIR>          StacksReverseOrder
02/19/2020  08:08 AM    <DIR>          SumOfTwo
01/04/2020  07:51 AM    <DIR>          TheGridSearch
12/11/2019  10:09 AM    <DIR>          ToTrieOrNotToTrie

# **** ****
C:\Users\John\workspace7>cd AorB

# **** ****
C:\Users\John\workspace7\AorB>dir /A
02/29/2020  09:10 AM    <DIR>          .
02/29/2020  09:10 AM    <DIR>          ..
02/29/2020  09:10 AM    <DIR>          .git
02/29/2020  09:10 AM               285 README.md

Once done I cloned the repository from GitHub. We are missing the code which we will implement in a Solution.java file to be created using VSCode.

3
8
2B
9F
58
5
B9
40
5A
2
91
BE
A8

8
58
18
42
-1


3
25
B631EB5AE
601C227E1
707AC8792
12
CAF7028FD
59B5AC1CE
CAF1B7B7F
3
81B9BB94E
8AB3CA95E
8BBBFB95E

C8582
707A00790
8AF10287D
48B1B534E
B9BB94E
8BB3CA95E

The first example is from the challenge. The first line contains the number of test cases. Each test contains four lines. The first is the number of bits that we can flip. The following two numbers is hexadecimal represent the A and B values. The last number of the set represents the C value. The set of numbers repeats for the three cases.

The second example is one I purchased using 5 hackos. When I implemented the code it worked with the sample case, but I was going to use two consecutive loops and for starters only implemented the first one which is fine using the test on the requirements page. Perhaps I did not need to purchase the test case, but I did. After that I implemented the second loop and it timed out on 4 out of 21 test cases. More on this as we see the solution.

Also note that in the first test case, the last set of numbers does not produce a viable solution. For this reason we just print a -1.

The test scaffolding provided is simple and to the point.

  // **** open scanner ****
  private static final Scanner sc = new Scanner(System.in);

  /**
   * Test scaffolding. 
   */
  public static void main(String[] args) {
    
    // **** read the number of test cases ****
    int q = Integer.parseInt(sc.nextLine().trim());

    // ???? ????
    // System.out.println("main <<< q: " + q);

    // **** loop onec per test case ****
    for (int i = 0; i < q; i++) {

      // **** read k ****
      int k = Integer.parseInt(sc.nextLine().trim());
    
      // **** read string for A ****
      String a = sc.nextLine();

      // **** read string for B ****
      String b = sc.nextLine();

      // **** read string for C ****
      String c = sc.nextLine();

      // **** ****
      aOrB(k, a, b, c);
    }

    // **** close scanner ****
    sc.close();
  }

As usual I added some comments. Not sure there is much to add.

  /**
   * Complete the aOrb function below.
   * 
   * Uses StringBuilder for bit manipulations (seem to be too slow).
   * Passed 17 or 21 test cases; 4 test cases timed out :o(
   * 
   * Use character arrays for bit manipulations.
   * Passed all 21 test cases :o)
   */
  static void aOrB(int k, String a, String b, String c) {

    // **** hex string to big integer ****
    BigInteger abi = new BigInteger(a, 16);
    BigInteger bbi = new BigInteger(b, 16);
    BigInteger cbi = new BigInteger(c, 16);

    // **** big integer to string builder ****
    StringBuilder asb = new StringBuilder(abi.toString(2));
    StringBuilder bsb = new StringBuilder(bbi.toString(2));
    StringBuilder csb = new StringBuilder(cbi.toString(2));

    // ***** compute the max length for the strings ****
    int maxLength = Math.max(asb.length(), bsb.length());
    maxLength = Math.max(maxLength, csb.length());

    // **** get all strings to the same length (prepend 0s) ****
    while (asb.length() < maxLength) {
      asb.insert(0, 0);
    }

    while (bsb.length() < maxLength) {
      bsb.insert(0, 0);
    }

    while (csb.length() < maxLength) {
      csb.insert(0, 0);
    }

    // **** convert string builders to character arrays ****
    char[] aca = asb.toString().toCharArray();
    char[] bca = bsb.toString().toCharArray();
    char[] cca = csb.toString().toCharArray();

    // **** first pass O(n) ****
    for (int i = 0; (i < maxLength) && (k >= 0); i++) {

      // **** for ease of use ****
      char aChar = aca[i];              // asb.charAt(i);
      char bChar = bca[i];              // bsb.charAt(i);
      char cChar = cca[i];              // csb.charAt(i);

      // **** cChar == '0' ****
      if (cChar == '0') {

        // **** 0 | 1 case ****
        if (aChar == '0' && bChar == '1') {
          bca[i] = '0';                 // bsb.replace(i, i + 1, "0");
          k--;
        }

        // **** 1 | 0 case ****
        else if (aChar == '1' && bChar == '0') {
          aca[i] = '0';                 // asb.replace(i, i + 1, "0");
          k--;
        }

        // **** 1 | 1 case ****
        else if (aChar == '1' && bChar == '1') {
          aca[i] = '0';                 // asb.replace(i, i + 1, "0");
          bca[i] = '0';                 // bsb.replace(i, i + 1, "0");
          k -= 2;
        }
      }

      // **** cChar == '1' ****
      else {

        // **** 0 | 0 case ****
        if (aChar == '0' && bChar == '0') {
          bca[i] = '1';                 // bsb.replace(i, i + 1, "1");
          k--;
        }
      }

      // **** check if no valid answer ****
      if (k < 0) {

        // **** output result ****
        System.out.println("-1");

        // **** nothing else to do ****
        return;
      }
    }

    // **** second pass O(n) ****
    for (int i = 0; (i < maxLength) && (k > 0); i++) {

      // **** for ease of use ****
      char aChar = aca[i];              // asb.charAt(i);
      char bChar = bca[i];              // bsb.charAt(i);
      char cChar = cca[i];              // csb.charAt(i);

      // **** 1 | 0 case ****
      if (cChar == '1' && aChar == '1' && bChar == '0' && k >= 2) {
        aca[i] = '0';                   // asb.replace(i, i + 1, "0");
        bca[i] = '1';                   // bsb.replace(i, i + 1, "1");
        k -= 2;
      }

      // **** 1 | 1 case ****
      else if (cChar == '1' && aChar == '1' && bChar == '1') {
        aca[i] = '0';                   // asb.replace(i, i + 1, "0");
        k--;
      }
    }

    // **** convert char array to string builder ****
    asb = new StringBuilder(new String(aca));
    bsb = new StringBuilder(new String(bca));

    // **** convert string builder string to big integer ****
    abi = new BigInteger(asb.toString(), 2);
    bbi = new BigInteger(bsb.toString(), 2);

    // **** output results in hexadecimal format ****
    System.out.println(abi.toString(16).toUpperCase());
    System.out.println(bbi.toString(16).toUpperCase());
  }

The comment for the function / method states that I attempted to use first use manipulations on StringBuilder objects. That allowed the code to pass all except 4 test cases. They timed out. I was going to rewrite the method on a second copy but decided to just modify the existing one. I left commented out the original code segments. As you can tell the logic is quite similar, just applied to a different data structure (in this case to character arrays).

I started converting the strings to BigIntegers. That took care of the hex conversion.

The StringBuilders provided a way to get to a binary representation of the hexadecimal values.

I then compute the length of the maximum string. We want all binary strings to have the same length. With that value in hand we prepend ‘0’s until all strings have the same count of bits.

Now we populate character arrays for the three values. The operations should be quite faster than using StringBuilders.

The first loop is used to replace bits in the A and B values in order to match C. If the target bit in C is ‘0’ we have three cases to address. If the bit value in C is ‘1’ we only have a single case. Note that we are decrementing the value of k as we process bits. If we exceed the maximum number of changes we print -1 and return.

If we have additional bits to change we go for a second round. We start by extracting the values into variables. We could just work directly with the arrays but if the tests pass we can leave them. It is easier to follow and maintain, not that we will need to maintain this code after it is completed.

We have to address two cases. What we want is to reduce the value of A and B using the remaining number of changes.

Once the loop is completed, we convert the character array to a StringBuilder of binary values. We then convert the binary values to hexadecimal. Finally we display the results in UPPER case. Not sure if that was stated in the requirements. The first test case only generates values that can be expressed in decimal. The second test case displays hexadecimal values in UPPER case. This implies that we need to convert them to UPPER case.

The code passed all test cases.

We now need to update the code in our repository.

# **** ****
C:\Users\John\workspace7\AorB>dir
02/29/2020  09:10 AM               285 README.md
03/03/2020  08:19 AM             5,361 Solution.java

# **** ****
C:\Users\John\workspace7\AorB>git status
On branch master
Your branch is up to date with 'origin/master'.

Untracked files:
  (use "git add <file>..." to include in what will be committed)

        Solution.java

nothing added to commit but untracked files present (use "git add" to track)

# **** ****
C:\Users\John\workspace7\AorB>git add Solution.java

# **** ****
C:\Users\John\workspace7\AorB>git status
On branch master
Your branch is up to date with 'origin/master'.

Changes to be committed:
  (use "git reset HEAD <file>..." to unstage)

        new file:   Solution.java

# **** ****
C:\Users\John\workspace7\AorB>git commit -m "initial pass"
[master 23f86a9] initial pass
 1 file changed, 183 insertions(+)
 create mode 100644 Solution.java

# **** ****
C:\Users\John\workspace7\AorB>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 8 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.54 KiB | 790.00 KiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/AorB.git
   4a1e271..23f86a9  master -> master

# **** ****
C:\Users\John\workspace7\AorB>git log
commit 23f86a935ee4c64eceb1de53d8771524ffcf31d8 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Tue Mar 3 08:24:57 2020 -0600

    initial pass

commit 4a1e2710b34990cf65d8930eee63b361abb95a20
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date:   Sat Feb 29 09:09:33 2020 -0600

    Create README.md

We commit the Solutions.java file and push the change to our GitHub repo. We are almost done. After generating the post in WordPress I will put the link to it in the README.md file. I will do that by editing it in GitHub.

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!

One last thing, thanks to all 375 subscribers to my blog!!!

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.