Check If an Integer's Bit Representation Is a Palindrome

Question: how can you determine if a positive integer is a palindrome. For example, 5 is a palindrome because 5 = 101. Also, 9 is a palindrome because 9 = 1001.

Solution: an integer is palindrome when its bit representation is the same reading from left to right or from right to left. Thus, in order to know if it is a palindrome or not, we just have to check if the number's value is still the same when we read the number's bits backward (right to left). For example, 5 is 101 and when we read its bits from right to left, which is 101, the result is still 5. However, 4 is 100 and when read backward it becomes 001 which is 1, so 4 is not a palindrome.

Pseudocode: here is the pseudocode for the algorithm:

integer nResultNum = 0
integer nInputNumCopy = nInputNum

while nInputNumCopy > 0
  nResultNum = nResult << 1;
  if nInputNumCopy & 1 == 1
    nResultNum = nResultNum | 1;
  nResultNumCopy = nResultNumCopy >> 1;
end while

if nResultNumCopy == nInputNum 
  return true

return false

Here is the implementation of the pseudocode using JavaScript:

function bIsIntPalindrome(nInputNum)
{
   if (nInputNum === 'undefined' || nInputNum === null || nInputNum < 0)
      return false;

   var nInputNumCopy = nInputNum;
   var nResultNum = 0;

   while (nInputNumCopy > 0)
   {
      nResultNum <<= 1;

      if (nInputNumCopy & 1)
      {
         nResultNum |=1;
      }

      nInputNumCopy >>= 1;
   }

   if (nInputNum == nResultNum)
      return true;

   return false;
}

Explanation: the general plan is to generate a number whose bit representation is the reverse of that of the input number. After that, we check to see if the two numbers equal. If they do, the input number is palindrome as explained above:

1. Check for invalid inputs.
2. nResultNum is the number whose bit representation is the reverse of the input number. nInputNumCopy is the copy of the input number. Since we'll destroy the value in the process, we must make copy of it so that we can compare the result to the original input later on.
3. The while loop runs until nInputNumCopy is 0, meaning that we have copied all of its bits. In other words, this loop copies the bits from nInputNumCopy to nResultNum from right to left. At each iteration:
   • First, shift nResultNum's bits to the left by 1
   • Second, check if the current right most bit in nInputNumCopy is 1 by using & operator. If the right most bit is 1, turn the right most bit of nResultNum to 1 using | operator.
   • Third, shift all bits of nInputNumCopy to the right by 1.
4. When finishing copying the bits from right to left, we check for equality between nInputNum (the original input value) and nResultNum (containing the same number of bits but in reverse order). If the two equal, then input number is palindrome, otherwise not.

Example: let's check to see if 5 is a palindrome. At the start of while loop, variables' values are nResultNum = 0 and nInputNumCopy = 5 (101). Entering the while loop:

1. First iteration, nResultNum <<= 1 still equals 0 because 000 << 1 = 0. nInputNumCopy & 1 = 1 because 101 & 001 = 001, so nResultNum |= 1 = 000 | 1 = 001. Then, nInputNumCopy >>= 1 = 2 because 101 >> 1 = 010 which is 2. Because nInputNumCopy > 0, loop continues.
2. Second iteration, nResultNum <<= 1 makes nResultNum = 010 because 001 << 1 = 010. Since nInputNumCopy & 1 = 0 (010 & 001 = 000), nothing added to nResultNum in this iteration. nInputNumCopy >>= 1 = 001 = 1. Since nInputNumCopy is still greater than 0, the loop continues.
3. Third iteration, (nResultNum <<= 1) = (010 << 1) = 100. (nInputNumCopy & 1) = 001 & 001 = 001, so a 1 bit is added to nResultNum such that (nResultNum |= 1) = (100 | 1) = 101. Shift nInputNumCopy to right by 1, making nInputNumCopy = 000. Since nInputNumCopy is now 0, the loop ends.

After the while loop, nResultNum = 101 which is 5. Thus, nResultNum equals nInputNum. The method returns true. 5 is a palindrome. We're done.

I hope the explanation was clear. If you have any question, please feel free to ask by emailing or posting in the comment section. Until next time!

Search for Intersection Between Two Sorted Arrays of Integers

Question: there are two sorted arrays of integers such as array(1, 3, 6, 9, 10) and array(-2, 0, 4, 6, 12). Search for the intersection between these arrays. The intersection is 6 at index 2 and index 3 in the example arrays.

Solution: a naive solution would be to compare each element in the first array to each element in the second array, resulting in an O(N * M) algorithm where N and M are the numbers of elements in first and second array respectively. A better solution is using binary search for each element in the first array in the second array. That is an O(N LogM) algorithm. However, we can even do better using two array iterators at a time. Take a look at the pseudocode below:

it1, it2
while it1 < size1 and it2 < size2
  if (array1[it1] == array2[it2])
    print(it1 and it2)
    return
  else if (array1[it1] > array2[it2])
    it2++
  else
    it1++

We simply move the iterators, one for each array, whenever an element of one array is less that the element of the other array. We do this until we either find the common element (intersection) or we reach the end of any array. This works because both arrays are sorted in the ascending order. Thus, we don't have to compare each and every element to all other elements to know where the intersection is. Here is the implementation of the pseudocode in JavaScript :)

function vIntersectionInSortedArrays(cIntArray1, cIntArray2)
{
   if (cIntArray1 === null || cIntArray1 === undefined 
      || cIntArray2 === null || cIntArray2 === undefined)
   {
      document.write("Empty arrays!"); 
      return;
   }

   var nArray1It = 0;
   var nArray2It = 0;
   
   while (nArray1It < cIntArray1.length 
         && nArray2It < cIntArray2.length)
   {
      if (cIntArray1[nArray1It] == cIntArray2[nArray2It])
      {
         document.write("Intersect at index" + nArray1It 
                        + " and " + nArray2It);
         return;
      }
      else if (cIntArray1[nArray1It] > cIntArray2[nArray2It])
         nArray2It++;
      else
         nArray1It++;
   }

   document.write("No intersection!");
}

I know it's unusual to use JavaScript but a break from C++ and Java is nice. As we expect, this algorithm is more efficient. In the worst case, it takes only O(M + N) time to return the answer!

As always, thanks for following and if you have any suggestion, please don't hesitate to let me know in the comment section.