Sorted Array to Red-Black Tree

(Note: Red-Black Tree is a Balanced Binary Search Tree)

Your teachers must have told you this about searching in an array: If you have a sorted array, then one of the most efficient way to find position of any element in that array is binary search.

I say: Fine, then why not just convert that array to a Red-Black Tree ? I find Red-Black Tree as a better option, as in binary search, you have to calculate the midpoint in every iteration/recursive-call during search.

Before you see the code, I must add: if the size of your array is N, then this code will generate N number of objects of Node class. Add to that, in each of these objects there are going to be 4 variables of 32bits each [Or on a 64 bit machine: 2 variables of 32 bit (the 2 integers) & 2 variables of 64 bit (the 2 object references)].

/*
 * Programming language: Java
 */

class RedBlackTree
{
  static class Node
  {
    int key;
    int value;
    Node left;
    Node right;
    Node(int key,int value)
    {
      this.key = key;
      this.value = value;
    }
  }

  Node root;

  public RedBlackTree(int[]sorted_integers)
  {
    root = arrayToRedBlackTreeRoot(sorted_integers,0,sorted_integers.length-1);
  }

  static Node arrayToRedBlackTreeRoot(int[]integers,int i,int j)
  {
    if(i>j)
      return null;
    int x=(j+i)/2;
    Node local_root=new Node(integers[x],x);
    if(i<j)
    {
      local_root.left = arrayToRedBlackTreeRoot(integers,i,x-1);
      local_root.right = arrayToRedBlackTreeRoot(integers,x+1,j);
    }
    return local_root;
  }

}

The code written above, is only to get you started. An actual application where you may have to write a similar code can be different, and you have to adjust parts of this code to suit your requirement. Here is one such example:
There are 2 arrays. One array contains phone/mobile numbers, and the other array contains names of owners of each number. eg: if number[4]=9876543210 and name[4]="John Ray", then John Ray's number is 9876543210. You are asked to write a program that finds the name of the person when you have that person's number. For that first make following changes/additions in the above code:

1. Change type of integers and sorted_array to long[]
2. Change type of key to long
3. Add a function named find in the class RedBlackTree

  /*
   * Programming language: Java
   */
  public int find(long key)
  {
    Node node=root;
    while(node!=null)
    {
      if(node.key==key)
        return node.value;
      else if(node.key<key)
        node=node.right;
      else if(node.key>key)
        node=node.left;
    }
    return -1;
  }

4. Write the folllowing in your main() function:

  /*
   * Programming Language: Java
   */
  long[]numbers=new long[10];
  String[]names=new String[10];
  // Home Work: Write code to initialize both arrays from any input.

  // bubble sort starts here: (you can choose your favourite algorithm)
  for(int i=0 ; i<numbers.length ; ++i)
    for(int j=1,n=numbers.length-i; j<n ; ++j )
      if(numbers[j-1]>numbers[j])
      {
        long temp_number=numbers[j-1];
        numbers[j-1]=numbers[j];
        numbers[j]=temp_number;
        String temp_name=names[j-1];
        names[j-1]=names[j];
        names[j]=temp_name;
      }
  RedBlackTree tree=new RedBlackTree(numbers);
  long number_x = 9876543210L;// Home Work: Read this number from input.
  int found=tree.find(number_x);
  System.out.println("The number: "+number_x+", belongs to "+(found==-1?"nobody":names[found]));

Though the above written code can work to give you a fair result, this may not be the most efficient way to write a program.
This is where the concept of MAP comes in. In C++, STL has map.h for it. In Java programming language an implementation of java.util.Map will do. But what change in above code will do it for us? The answer is: Instead of puting index of names in value, put the name itself as value. Thats it! So finally, we have a code that looks like this:

/**
 * Programming Language: Java
 * @author Abhishek
 */
class RedBlackTree {

    static class Node {

        long key;
        String value;
        Node left;
        Node right;

        Node(long key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    Node root;

    public RedBlackTree(long[] numbers,String[]names) {
        root = arrayToRedBlackTreeRoot(names,numbers, 0, numbers.length - 1);
    }

    static Node arrayToRedBlackTreeRoot(String[]names,long[] numbers, int i, int j) {
        if (i > j) {
            return null;
        }
        int x = (j + i) / 2;
        Node local_root = new Node(numbers[x], names[x]);
        if (i < j) {
            local_root.left = arrayToRedBlackTreeRoot(names,numbers, i, x - 1);
            local_root.right = arrayToRedBlackTreeRoot(names,numbers, x + 1, j);
        }
        return local_root;
    }

    public String find(long key) {
        Node node = root;
        while (node != null) {
            if (node.key == key) {
                return node.value;
            } else if (node.key < key) {
                node = node.right;
            } else if (node.key > key) {
                node = node.left;
            }
        }
        return "nobody";
    }
}

public class NameNumber {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        long[] numbers = new long[10];
        String[] names = new String[10];
        // Home Work: Write code to initialize both arrays from any input.(file/console)

        // bubble sort starts here: (you can choose your favourite algorithm)
        for (int i = 0; i < numbers.length; ++i) {
            for (int j = 1, n = numbers.length - i; j < n; ++j) {
                if (numbers[j - 1] > numbers[j]) {
                    long temp_number = numbers[j - 1];
                    numbers[j - 1] = numbers[j];
                    numbers[j] = temp_number;
                    String temp_name = names[j - 1];
                    names[j - 1] = names[j];
                    names[j] = temp_name;
                }
            }
        }
        RedBlackTree tree = new RedBlackTree(numbers,names);
        long number_x = 9876543210L;// Home Work: Read this number from input.
        System.out.println("The number: " + number_x + ", belongs to " + tree.find(number_x));

    }
}
 

You can also replace the statement return "nobody" with return null in the code above. Also try thinking of some programming cases where a number-to-object map can be replaced with this code. Like: where you may have used java.util.HashMap<Long,String>(in Java).

Zero Factorial is One

Ever looked for a simple explanation for: why 0!=1 ?

I am sure your teachers may have explained you through this:
 n! = (n-1)!n
 hence, 1! = 0!1
 dividing both sides by 1, 1! / 1 = 0!1 / 1
 hence 1 = 0!

But here I am going to explain in a different way.

Look at this set: {a,b,c}. It has 3 elements: a , b , and c . Now arrange all these elements in different ways, and let us see how many different arrangements are possible.

 Arrangement 1: {a,b,c}

 Arrangement 2: {b,c,a}

 Arrangement 3: {c,a,b}

 Arrangement 4: {a,c,b}

 Arrangement 5: {c,b,a}

 Arrangement 6: {b,a,c}
So with a set of 3 elements, 6 arrangements are possible. So we have 3! = 6.


Similarly this set: {a,b}, with 2 elements has 2 possible arrangements: {a,b} and {b,a}. That makes 2!=2.

Similarly this set: {a}, with 1 element has 1 possible arrangement: {a}. That makes 1!=1.

Now look at this set, it has no element: {}.
In how many ways can you arrange it's elements ? The answer is, there is only 1 possible arrangement: {}.
So that brings us to this result: 0!=1

Average Without Overflow

Puzzle:

There are 10 numbers, each has values between 0 to 99. Write computer program to find the average of those 10 numbers, such that the total must never exceed 99 (at any point during or after iteration).

Answer:

/*
 * First Approach
 * Programming language: Java
 */
int[]number=new int[10];
// initialize number
int absolute_average=0,sum_of_remainders=0;
for(int i = 0 ; i < 10 ; ++i)
{ absolute_average+=number[i]/10;
  sum_of_remainders+=number[i]%10;
  if(sum_of_remainders>10)
  { absolute_average+=sum_of_remainders/10;
    /* or better:
    absolute_average+=1;
    (as sum_of_remainders cannot be more than 18 with this if-block in place.)
    */
    sum_of_remainders%=10;
  }
}
float average=absolute_average+(sum_of_remainders/10.0F);
// or :
//float average=((float)absolute_average)+(((float)sum_of_remainders)/10);

/*
 * Alternate Approach
 * Programming language: Java
 */
byte[]number=new byte[10];
// initialize number
double average=0.0;
for(int i = number.length ; --i > -1 ; )
  average+=number[i]/10.0;


Reason:

(x[1]+x[2]+.....+x[n])/n = (x[1]/n)+(x[2]/n)+.....+(x[n]/n)

Need for this puzzle:

Programming in similar way can be useful in preventing bit-overflow in a computer program.
More Explanation:
For example, int in Java can store a value between Integer.MIN_VALUE and Integer.MAX_VALUE, and any attempt to assign a number out of those bounds (which can happen during addition, subtraction, or multiplication) will result in bit-overflow and loss of precision. So is with byte(between Byte.MIN_VALUE and Byte.MAX_VALUE), short(between Short.MIN_VALUE and Short.MAX_VALUE), and long(between Long.MIN_VALUE and Long.MAX_VALUE).