Algorithm: Reverse an integer

Problem: Reverse an integer
17 reverses to 71
9 reverses to 9
-2367 reverses to -7632
*** space overhead NOT allowed

Solution

This problem can be easily solved if space overhead is allowed. You can convert the integer into a string and then reverse the string and parse back string into an integer. But what makes this problem interesting is if you have to do it without any space overhead (except that of the result). Below is the Java implementation of the same. 

     /**  
       * Reverse a integer (handles negatives also)  
       *   
       * @param num  
       * @return  
       */  
      public static int reverseNum(int num) {  
           boolean negative = false;  
           if (num < 0) {  
                num = -num;  
                negative = true;  
           }  
           int reverse = 0;  
           while (num > 0) {  
                reverse = reverse * 10 + num % 10;  
                num /= 10;  
           }  
           if (negative) {  
                reverse = -reverse;  
           }  
           return reverse;  
      }  

Note: What if number overflows? 
If the number overflows the reversed number will not fit in the integer data type.
One of the possible ways would be to store reversedNum in long and then check if it's value is out of integer range and then do something like below:

if(reverse > Integer.MAX_VALUE || reverse < Integer.MIN_VALUE) {
        return 0;
 } else {
        return (int) reverse;
 }

So refactor your code to make sure that overflow is taken into consideration. There are other ways to check if number overflows (like positive number will become negative). But, I think the above approach is much cleaner.

Checking if the number is a palindrome
This method can be used to check if a number is a palindrome.
if (reverse(num) == num ){
  //num is palindrome
}

--
keep coding !!!

Binary Search on a sorted file in Java

Binary search on a sorted array/list is quite trivial. But at times, you might get a file having sorted items and asked to find if a given item exists in it or not?

If the number of elements in the file is less, you can easily stream file in an array and then apply binary search. But what if the size of the file is huge or you don't have enough available memory to read the full content in an array. Can we apply binary search directly on file? YES!!!

Random Access File

Java I/O API provides a class named as RandomAccessFile. It has a different behavior than other InputStream or OutputStream classes. RandomAccesFile allows you to move forward and backward within the file using seek() method. It also provides length() method to give the maximum size of the file. And you can open a file either in read mode or read/write mode by passing "r" or "rw" in the constructor. 

Write sorted integers to a file:

 RandomAccessFile file = 
               new RandomAccessFile("sortedFile.txt", "rw");

for (int i = 0; i < 10; i++) {

file.writeInt(i * i);

}

file.close(); 

Java Implementation 

Below binary search implementation on a file.

 /**
  * Binary search
  * 
  * @param fileName
  *            input file name
  * @param num
  *            target input to be searched
  * @return true if search is successful
  */
 public boolean binarySearch(String fileName, int num) {
  Objects.requireNonNull(fileName, "valid filename is required !");

  // printFile(fileName);
  try {
   RandomAccessFile raf = new RandomAccessFile(fileName, "r");
   int first = raf.readInt();
   if (num == first)
    return true;

   int count = (int) (raf.length() >> 2);
   int midIndex, midValue, endIndex = count - 1, startIndex = 0;

   while (startIndex <= endIndex) {
    midIndex = (endIndex + startIndex) >> 1;

    // move file pointer to midIndex
    raf.seek(midIndex * 4);

    midValue = raf.readInt();
    if (midValue == num) {
     return true;
    } else {
     if (midValue > num) {
      endIndex = midIndex - 1;
     } else {
      startIndex = midIndex + 1;
     }
    }
   }
   raf.close();
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  }
  return false;
 }

--
keep coding !!!

Bit Vector

The bit vector is also referred to as bit-array or bit-set. As the name suggests, it's array of bits. Every modern programming language supports primitive or basic data types like byte, integer, short etc which are inherently array of bits only. So, is bit-array different? 

A byte is composed of 8-bits. Literally, byte data type is also a bit-array of 8 bits or 1 byte.  Integer data type of 4 bytes is a bit-array of 32 bits and so on. This is where the similarity stops and life of bit-array begins. 

To understand it further let's take an example. Assume that you want to represent a set of integers in the range of 0 and 999 (both are inclusive). An option which you have as a programmer is; store these integers in an array of length 1000 or a list which can grow up to 1000. Remember, it's a set, so you are going to store only unique numbers in the range. 

//Java snippet

int[] set = new int[1000];

set[i] = num

What is the memory requirement of above?

Each integer takes 4 bytes. So total memory requirement for 1000 integers is 4KB (=4*1000 byte).  

can we improve? 

If the requirement says that not all numbers in the range might be present in the set, we can use ArrayList instead of an array. So this will improve a bit, as the numbers which are not in the set will not occupy any memory. This helps to an extent but worst-case memory requirement is still 4KB. 

can we improve?

As long as you going to store each element of the set in an integer, space overhead is going to remain the same.

Bit-Array

A bit can only take two values i.e. 0 or 1.  It can be used to denote the presence or absence of an item. So as discussed above, a byte is an array of 8 bits. This means these 8 bits can be used to represent presence/absence of an item in the set. Recall that in an integer array, the index is used to get element stored at that location. Similarly, in bit-set, bit at a position can be used to represent the presence of a number.

So as shown in the above figure, we can represent a set of integers in the range of 0 and 7, can be represented by just 1 byte ( or 8 bits). If the number is present make bit at the corresponding bit as 1. 

So below two operations can be performed on bit-set.

1. Setting an integer in the array
2. Testing if an integer exists in the array/set

Implementing Bit-vector

Now, let's return to our initial problem of storing integers in the range of 0 and 999. 

Number of bits required = 1000

Number of bytes required = 1000/8 = 125

So 1000 integers can be represented in 125 bytes.

Below is the Java implementation:

/**
 * Bit-vector to store integers
 * 
 * @author Siddheshwar
 * 
 */
public class BitArray {
 private byte[] set;

 public BitArray(int length) {
  int arraysize = length >> 3;

  // if length is not multiple of 8
  if (length % 8 != 0) {
   arraysize++;
  }
  this.set = new byte[arraysize];
 }

 /**
  * Set given number in the bit-array i.e. make corresponding bit as 1
  * 
  * @param number
  */
 public void storeNumber(int number) {
  if (number > (set.length << 3) || number < 0) {
   throw new IllegalArgumentException("number out of range");
  }

  int arrayIndex = this.getArrayIndex(number);
  int bitIndex = this.getBitIndex(number);

  // shift 1 to the bit index
  int pos = 1 << bitIndex;

  // so bit at position needs to be made 1
  this.set[arrayIndex] = (byte) (this.set[arrayIndex] | pos);
 }

 /**
  * Check if the number exists in the array if the corresponding bit is 1
  * then number exists
  * 
  * @param number
  */
 public boolean numberExists(int number) {
  if (number > (set.length << 3) || number < 0) {
   throw new IllegalArgumentException("number out of range");
  }

  int arrayIndex = this.getArrayIndex(number);
  int bitIndex = this.getBitIndex(number);

  // shift 1 to the bit index
  int pos = 1 << bitIndex;

  // check bit at position is 0 or 1
  return (this.set[arrayIndex] & pos) > 0 ? true : false;
 }

 private int getArrayIndex(int number) {
  return number >> 3; // divide by 8
 }

 private int getBitIndex(int number) {
  return number % (1 << 3); // % 8
 }

 private void printSet() {
  System.out.println("\n array content :");
  for (int i = 0; i < set.length; i++)
   System.out.print(Integer.toBinaryString(this.set[i]));
 }

 //test method
 public static void main(String[] args) {
  BitArray array = new BitArray(1000);
  System.out.println("length of array :" + array.set.length);

  int num1 = 17;
  array.storeNumber(num1);

  int num2 = 171;
  array.storeNumber(num2);

  int num3 = 400;
  array.storeNumber(num3);

  System.out.println("val " + num1 + " exists ? "
    + array.numberExists(num1));
  System.out.println("val " + num2 + " exists ? "
    + array.numberExists(num2));
  System.out.println("val " + num3 + " exists ? "
    + array.numberExists(num3));
  System.out.println("val " + 500 + " exists ? "
    + array.numberExists(500));

  for (int i = 0; i < 1000; i = i + 2)
   array.storeNumber(i);

  array.printSet();

  /*
   * for(int i = 0; i< 1000; i++) System.out.println(array.get(i));
   */
 }
}

Output:
length of array :125
val 17 exists ? true
val 171 exists ? true
val 400 exists ? true
val 500 exists ? false

 array content :
10101011010101101011110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110111011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101

---
keep coding !!!

Generate random number sequence without duplicates

Problem is: given a number, say 5;
Generate unique random number sequence between 1 and 5 (both included) like 3, 4, 5, 2, 1 or 1, 4, 5, 2, 3 etc.

Default approach will not ensure that sequences are unique. So, ensuring that the sequence is unique makes this problem interesting. 

I will be solving this problem in Java, using java.util.Random API. The approach is generic and hence can be employed in any programming language. 

Unique Random Sequence

As discussed, generating unique random sequence makes this problem interesting. This is because inbuilt API doesn't return unique sequence if you call nextInt(n) repeatedly. Below snippet confirms it.

  Random r = new Random();
for(int i=0; i<5; i++){
System.out.print(r.nextInt(5)+" ");
}
  //Produces : 4 4 0 0 2

Every time the nextInt method is called, the probability of getting a positive number less than 5 is equal. And hence number in the output could get repeated. On your system, you might get a different sequence but duplicates will still be there (run above snippet multiple time).

This can be solved by taking an array of given size and pre-populating it with unique numbers in the range. And then using the random number generator to shuffle these numbers. Above diagram illustrates its working.

           
                         r = rand.nextInt(5);

if r = 1; this means that value at pos(0) (or first element) should occupy the last position in the array.

So the first element will get swapped with the last element. Above diagram shows that the probability of occupying the last position is equal for all values. Once this is done, now all elements except the last one compete to occupy second last position.

So the generated random number could repeat, but the value at that position in the array is unique and it keeps on changing so the output is always going to be unique.

Java Implementation

Given below a Java method which generates a unique random number. 

 /**
  * Generate random number without duplicates in range 1,2..n Both 1 and n
  * are included
  * 
  * @param n
  *            up to number
  * @return List<Integer> randomly generated list
  */
 public List<Integer> generate(int n) {
  List<Integer> arr = new ArrayList<>(n);
  for (int i = 0; i < n; i++) {
   arr.add(i + 1);
  }
  System.out.println("input  :" + arr);

  Random rand = new Random();
  int r; // stores random number
  int tmp;

  //shuffle above input array
  for (int i = n; i > 0; i--) {
   r = rand.nextInt(i);
   
   tmp = arr.get(i - 1);
   arr.set(i - 1, arr.get(r));
   arr.set(r, tmp);
  }
  return arr;
 }

Output: [3, 4, 5, 2, 1]

---
keep coding !!!