To quote Miley Cyrus, ‘it’s the CLIMBBBBBBBbbBbBB!!!!’

A Coding Challenge Review

Converting a number of base 10 to its inverse binary complement, segregating arrays in JavaScript, and oh God I don’t know what that means

For a recent coding challenge I had 90 minutes to complete a handful of logic puzzles. Among them were these 2:

1. Given an integer of base 10 return the inverse binary complement of that number. A complement of a number is defined as inversion (if the bit value = 0, change it to 1 and vice-versa) of all bits of the number starting from the leftmost bit that is set to 1. For example, if N = 5, N is 101 in binary. The complement of N is 010, which is 2 in decimal.

Initial thoughts: (Sprints to the bathroom to vomit……………… nah I’m just playing). Um…..WUT? Oh god. Panic settles in just like Guy Fieri saddling up to a gargantuan bowl of New Mexico green chili. It’s been quite long since I’ve dealt with binary numbers ( a few presentations at bootcamp about bits and bites), a wee longer since I’ve actually had to convert numbers to binary (college comp sci class 101, a.k.a. 5 years ago), and even centuries longer since I’ve had to memorize the meaning of base 10. Luckily, this ain’t my first time at the rodeo. Baby steps Brendanopolis, you got this.

I quickly looked up what a base 10 number was (base 10 refers to the way our number system is structured in decimals. Each decimal/place has 10 possible options from 0 to 9). Ok. duh. Next. How do you convert a number in base 10 to binary? Thank the sweet lord for Anthonette:

Ok. Things are looking up. Not going to worry about when a number passed in is more than 255 (aka the max number my function can take for converting the number into an 8-bit system).

My pseudo code:

1. Iterate over my each number in my comparison operators to check to see if it is greater than my number. If it is, that means the 8 bit binary representation of this base 10 number will have a 0, so add it my accumulating binary string. If it does not, it will be a 1, so push 1 to the accumulating binary number and update the value of my number to equal my number minus the current binary comparison (hmm… seems like a good time to use reduce?).
2. Once I have the binary representation of that number I need to convert it to its inversion. The directions say a complement is an inversion of all bits of the number starting from the leftmost bit that is set to 1. That means that if I take my string and convert it to an integer with parseInt() it should return only the number from the leftmost bit, knocking off any excess 0’s that my binary generator has built. All I have to do is swap the 0s and 1s of what’s remaining to have my inverse… at least I thought.
3. The trickiest part of this function was making sure that parsing the inverse of the binary did not knock off any 0s that I needed. For instance 5 in binary is 101, the inverse of 101 is 010. Calling parseInt(‘010') would return 10, which is NOT the answer. 010 in binary is 2 in base 10. Turns out parseInt() takes 2 arguments: the thing you want to parse and a radix.
4. A radix is a fancy word for the number of values for a single digit. I did not realize this till the very end of writing my function and I had about 53 seconds to submit my code. parseInt(inverseBinary, 2) did the trick (2 for binary 😏 ).

My function:

function inverseBinaryComplement(num) {
  let binaryComparisons = [128, 64, 32, 16, 8, 4, 2, 1];
  let copyOfN = num;
  let binary = '';
  let inverseBinary = '';
  
  for (let comparison of binaryComparisons) {
    if (comparison > copyOfN) {
      binary = binary + 0;
    } else {
      binary = binary + 1;
      copyOfN = copyOfN - comparison
    }
  }
  
// this takes care of the excess 0s
  binary = parseInt(binary).toString();
  console.log(binary)
  
  
  for (let num of binary) {
    if (num === '1') {
      inverseBinary = inverseBinary + 0;
    } else {
      inverseBinary = inverseBinary + 1;
    }
  }
  return parseInt(inverseBinary, 2)
  
}

Now for the much cleaner way of doing things:

function inverseBinaryComplement(num){ 
   let binary = parseInt(num).toString(2); 
   let complement = ""; 
   for (let i in binary)  {
     complement = complement + ((binary[i] === "1") ? 0 : 1);
   } 
   return parseInt(complement, 2);
}

2. Given an unordered array put the even numbers on the left side of the array and the odds on the right in the least number of ‘swaps’ possible. A swap is defined as taking a number at a certain index and switching it with the index of another number and vice versa. Return the number of swaps.

Initial thoughts: Oh god… (sprints to the bathroom.. again). What do they want? Some sort of sorting algorithm? Merge sort? Heap sort? Asymptotic time complexity? To be honest, I actually ended up running out of time and never finished the problem, but I did eventually write a solution that worked.

My pseudo code:

1. First things first. I need a way to move the odds from the left and evens to the right all the while making sure I know where that boundary between even and odd is.
2. I also need to increase my counter for ‘swaps’ every time I make a swap.
3. If the element I am looking at on the left is even I can keep it there and move toward the middle. If the element I am looking at on the right is odd I can keep it there and move toward the middle. Just as long as I have not crossed the boundary between even and odd, continue the process until I have. Once I have stop.

My function:

function seperateEvenAndOdd(arr) {
  let left = 0;
  let right = arr.length-1;
  let count = 0;
  while (left < right) {
      /* Read `while we're looking at the left-most element let's see if it's even and we haven't crossed over our middle point (where the even turn into odd) we can leave the current left element alone. Let's look at the next most left element.` */
      while (arr[left]%2 === 0 && left < right) {
         left++;
         console.log(arr[left])
      }
     /* Read `while we're looking at the left-most element let's see if it's even and we haven't crossed over our middle point (where the even turn into odd) we can leave the current right element alone. Let's look at the next most right element.` */
      while (arr[right]%2 == 1 && left < right){
        console.log(arr[right])
        right--;
      }
     /* If we reach this statement that means our current left element and our current right element is */
      if (left < right) {
        /* Swap arr[left] and arr[right]*/
        let swappedArr = swap(arr, left, right);
        console.log(swappedArr)
        left++;
        right--;
        count++;
      }
  }
  return count;
      
}
//helper function
function swap(array, a, b) {
    let newArr = array;
    let aValue = newArr[b];
    newArr[b] = newArr[a];
    newArr[a] = aValue;
    return newArr;
}

No fancy sorting algorithm was needed, though the time complexity of this one (a nested while loop inside a while loop is O(n²). Let me know if you can come up with a more efficient way of doing it. Peace!

Much appreciated for reading! I am always looking for feedback on my blogs and projects. Don’t be afraid to leave a comment or send me a message. Also on the journey of transitioning to a career in Software Development? I’d love to connect on Linkedin.

Enjoy my writing? Check out my other articles👇 down below.

Css3 grid or Flexbox

SQL Alchemy: Python’s ActiveRecord

So you want to host your Single Page React App on GitHub Pages?

Connecting AWS’s S3 to your Heroku hosted Rails App, or…

ActiveRecord, Dirty Attributes and Michael Jackson

Recreating Twitter’s `Like` effect with with mo.js