Problem #1

Little penguin Polo adores strings. But most of all he adores strings of length n.

One day he wanted to find a string that meets the following conditions:

1. The string consists of n lowercase English letters (that is, the string's length equals n), exactly k of these letters are distinct.
2. No two neighbouring letters of a string coincide; that is, if we represent a string as s = s₁s₂... s_n, then the following inequality holds, s_i ≠ s_i + 1(1 ≤ i < n).
3. Among all strings that meet points 1 and 2, the required string is lexicographically smallest.

Help him find such string or state that such string doesn't exist.

String x = x₁x₂... x_p is lexicographically less than string y = y₁y₂... y_q, if either p < q and x₁ = y₁, x₂ = y₂, ... , x_p = y_p, or there is such number r (r < p, r < q), that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 < y_r + 1. The characters of the strings are compared by their ASCII codes.

Input

A single line contains two positive integers n and k (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 26) — the string's length and the number of distinct letters.

Output

In a single line print the required string. If there isn't such string, print "-1" (without the quotes).

Sample test(s)

input

7 4

output

ababacd

input

4 7

output

-1

Solution

Solution for the above problem can be downloaded from here

Sum Of Subset (Using PowerSet)

for those who don't know sum of subset problem just google it.

But allow me to explain what is power set 

e.g. let X be an set, X = { 1,2,3}
then power set will contain = 2^n subset of set X, where n is no. of elements in set X
so our power set will contain total 8 subset of set X
power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
notice that the 1st set is a null set because a null set is a subset of every set.

Now consider sum of subset problem 
let X be an array which contains input from user let X = {1,2,3}
then power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
let m = 3

then the output of sum of subset problem is { {3},{1,2} }

if you are reading from beginning than now you must have a fair idea about what we are going to do, if you didn't understand than chill, the concept will be very clear in 5 minutes from now.

once we have computed the power set, we will take each individual set from the power set, if the power set contains only 1 element than we will compare that element with m if that element is equal to m than we will print that set as  1 of the solution, but if set contain multiple elements in it than we will add them all and compare the sum with m if it is equal than we will print the set. that's it!

Program:

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;


 //@author Naved Momin navedmomin10@gmail.com;

public class SumOfSubsets {


    public ArrayList powerSet(int a[]){
        ArrayList pw = new ArrayList();
        
        pw.add(" ");
        for (int i = 1; i <= a.length; i++) {
            ArrayList tmp = new ArrayList();
            
            for (String e : pw) {
                if(e.equals(" "))
                    tmp.add(""+a[i-1]);
                else
                    tmp.add(e+ " " + a[i-1]);
            }
            pw.addAll(tmp);
        }
       
        return pw;
    }
    int m ;
   
    
    public void navedsSOS( ArrayList p ){
        int sum = 0;
        System.out.println( "output: ");
        for (String string : p) {
            
                String[] split = string.split(" ");
                
                if(split.length > 1){
                    for (String no : split) {
                    sum += Integer.parseInt(no); 
                    }
                    if( sum == m){
                        if(!set.contains(string)){
                            set.add(string);
                            System.out.println( string );
                           
                        }
                    }
                    sum = 0;
                }else if( split.length == 1){
                    int k = Integer.parseInt(string);
                    if( k == m ){
                        if(!set.contains(string)){
                            System.out.println( " " + k );
                            set.add(string);
                        }
                    }

                }
            
        }
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SumOfSubsets s = new SumOfSubsets();
        s.init();
    }
    int n ;
    int arr[];
    Scanner s = new Scanner(System.in);
    Set set = new LinkedHashSet();
    private void init() {
        System.out.println( "enter n ");
        n = s.nextInt();
        System.out.println( "enter m ");
        m = s.nextInt();
        arr = new int[n];
        System.out.println( "enter elemets ");
        
        
        
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
                    
            //set.add(arr[i]);
        }
  
        ArrayList powerSet = powerSet(arr);
        navedsSOS(powerSet);
    }
}

outout:

Round Robin In Java

for those who don't know Round Robin algorithm

Program

import java.util.Scanner;

 
 //@author Naved Momin naved.spartans.rocks75@gmail.com/navedmomin10@gmail.com
 
public class SimpleRR {

    int [] temp;
    int commBT, k, tq;
    int[][] d;
    int btcache;

    
    void getData( ){
        Scanner s = new Scanner(System.in);
        System.out.println( "enter no. of process");
        int pcount = s.nextInt();
        d = new int[pcount][2];

        temp = new int[pcount];
        System.out.println( "enter BT");
        for (int i = 0; i < pcount; i++) {
            d[i][0] = i;

            int m = s.nextInt();
            d[i][1] = m;

            commBT += m;
        }
        System.out.println( "enter TQ ");
        tq = s.nextInt();
        start();
        display( );
        
    }
    void start( ){
        for (int i = 0; i < d.length; i++) {
            int bt  = d[i][1];
            if( bt > 0){
                if( bt <= tq){
                    temp[i] = btcache+bt;
                    btcache = temp[i];
                    k += bt;
                    bt -= bt;
                     
                }
                else{
                    temp[i] = btcache+tq;
                    btcache = temp[i];
                    bt -= tq;
                    k += tq;
                }
                
                d[i][1] = bt;
               
                
            }
        }
        if( k!= commBT)
            start();
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SimpleRR r = new SimpleRR();
        r.getData();
    }

    private void display() {
        float val = 0;
        int c = 1;
        for (int i : temp) {
            System.out.println( "BT for process " + c + " is " + i );
            val += i;
            c++;
        }
        System.out.println( "avg BT = " + val/temp.length);
    }
}

The above code finds & prints turn-around time & average turn around time for the given data.

Output

Finding Nth Largest Term In Unsorted Array

Given a task of finding nth largest term in an unsorted array by obeying following rules ...

Rules

1. You cannot sort an array
2. You cannot use a single library function (No API calls are allowed)
3. A separate copy of array should not be created

This can be easily implemented using a stack where we will start filling the stack with the smallest element, such that at the end we will get largest term at the top.

Algorithm:

1. accept array elements
2. determine the minimum element from the array
3. insert it into the stack
4. repeat step 2 & 3 until stack contains all elements of array
5. accept nth position from the user, say x
6. return the element which is stored at the x position
7. display the result
8. stop

Psuedo code for finding minimum element in an array

imin <-- 0;

        for ( i <-- 0; i < arr.length; i++) {

            imin <-- i;

            for (j <-- 0; j < arr.length; j++) {

                if( a[j] < a[imin] ){

                    imin <-- j;

                }

            }

        }

where " imin " stores index of the minimum element.

Code

package Kthlargestterm;

import java.util.Scanner;

 //@author Naved Momin(navedmomin10@gmail.com)
 
public class KthLargestTerm {

    static int[] a;
    static Scanner s = new Scanner(System.in);
    static int counter = 0;
    static StackUsingLL stack = new StackUsingLL();
    
    public KthLargestTerm(int size) {
        a = new int[size];
    }
    
    int getMin( ){
        int imin = 0;
        for (int i = 0; i < a.length; i++) {
            imin = i;
            for (int j = 0; j < a.length; j++) {
                if( a[j] < a[imin] ){
                    imin = j;
                }
            }
        }
        int k = a[imin];
        a[imin] = Integer.MAX_VALUE;
        return k;
    }
    
     
     static void getData( ){
        System.out.println( "enter size "); 
        int n = s.nextInt();
        KthLargestTerm kth = new KthLargestTerm(n);
        System.out.println( "enter data ");
        for (int i = 0; i < n; i++) {
            a[i] = s.nextInt();
        }
        
        int min = kth.getMin();
         int c = 0;
        while ( min != Integer.MAX_VALUE && c < n ) {             
            if(!stack.contains(min))
                stack.insert(min); 
            
            min = kth.getMin();
            c++;
         }
        
        System.out.println( "enter nTh position to view nth largest term ");
        int m = s.nextInt();
         while (m != -1) {     
             if( m >= 0 ) {
                    int item = stack.getItem(m);
                    String str =  (m == 1) ? "st" 
                            : (m==2) ? "nd" 
                            : (m == 3 ) ? "rd"
                            : "th";
                    
                    System.out.println( m + str +  " largest term is " + item );
                }
             System.out.println( "press -1 to exit or press any key to continue...");
             m = s.nextInt();
             if( m != -1 ){
                System.out.println( "enter nTh position to view nth largest term ");
                m = s.nextInt();
                
             }
         }
        
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        getData();
    
    }
}   




class Node{
    int data;
    Node next;
}

public class StackUsingLL {
 
    Node top ;
    static int insertAccount = 1;
    
    public boolean isempty( ){
       if( top == null ){
           return true;
       }else
           return false;
    }
    
    public void insert( int x ){
        Node newrec  = new Node();
        newrec.data = x;
        newrec.next = null;
        
        if( top == null ){
            top = newrec;
        }else{
        newrec.next = top;
        top = newrec;
        }

      insertAccount++;
    }
    
    public int delete( ){
        if( isempty() ){
            System.out.println( "stack empty" );
        return -1;
        }
        else{
            int x = top.data;
            top = top.next;
            return x;
        }
    }
    
    public boolean hasNext( ){
        
        if( top != null ){
            return true;
        }
        else{
            return false;
        }
    }
    
    public boolean contains( int min ){
        boolean val = false;
        Node p = top;
        while ( p != null ) {            
            if( stackTop( ) == min ){
                val = true;
                break;
            }
            else
                val = false;
            p = p.next;
        }
        return val;
    }
    
   public int getItem( int index ){
        if( index <= insertAccount ){
            int i = 1;
            int d = -1;
            Node p = top;
            while (p != null) {            
                if( index == i ){
                    d = p.data;
                    break;
                }
                i++;
                p = p.next;
            }
            return d;
        }else{
            System.err.println( "index was out of range ...");
            return -1;
        }
    }
    
    public int stackTop(){
        return top.data;
    }
    
    public void display( ){
        if( isempty() )
            System.out.println( "stack empty");
        else{
            Node p = top;
            while (p != null) {
                System.out.println( p.data + " ");
                p = p.next;
            }
        }
    }
    
}

Output

In case you want *.jar file then download it from here

Correct Implementation of Insertion Sort

Given a task of implementing insertion sort, many people end up with following code 

    
void insertionSort(int a[]){
 for (int i = 0; i < a.length; i++) {
                
                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }
                    
                }
 }
}

Although the code works as expected & sorts the given data in O(n^2) time, but this is the wrong implementation of insertion sort.

Do You Know Why ?

The reason is best case time complexity of insertion sort is O(n) but this code has O(n^2), in short no matter what sequence of data you through at this code it will take O(n^2) time i.e best, avg. & worst case time complexity of this code is O(n^2).

Note: If you have clear your "Analysis of Algorithms & Design" paper you will understand what is written above.

If you have understand the above statements than you can fix the wrong implementation on your own, the above implementation can be corrected by just adding one statement which i left it for you as an exercise.

In case you are in hurry you can adopt My way to write insertion sort

Correct Implementation 

    
 int[] insertionSort(int [] a ){
        for (int j = 1; j < a.length; j++) {
            int i = j-1;
            while ( ( i >= 0 ) && a[i] > a[i+1] ) {                
                int k = a[i];
                a[i] = a[i+1];
                a[i+1] = k;
                i -= 1;
            }
        }
        return a;
    }

The best case time complexity(i.e when array elements are already in ascending order) of this code is O(n) & worst case time complexity is O(n^2), which proves that this code is correct implementation of Insertion Sort.

Swapping Using 2 Variables

Some of mine friends asked me a question, the Question was

Agreed that we can swap two numbers using some math, but how can we swap two chars & string without using 3rd variable ?

This blog post will answer the question, the method i have used is preety simple & straight forward
We will do following swapping

• Number Swapping
• Chars Swapping 
• Strings Swapping

To begin with lets quickly see the codes

• Number Swapping

 void swappingNumbers( int a, int b ){

        System.out.println( "input value  a = " + a + "  b = " + b );
        a = a+b;
        b = a-b;
        a = a-b;
        System.out.println( "swapped values a = " + a + " " + " b = " + b );
    }

The above code swaps two ( signed & unsigned ) numbers without using any 3rd variable

• Chars Swapping 

 void swappingChars(char a, char b ){
        System.out.println( "input value  a = " + a + "  b = " + b );
        int p = (int)a ,q = (int)b;
        p =  ( ( (int) p ) + ((int)q) ) ;
        q = ( ( (int) p ) - ((int)q) ) ;
        p = ( ( (int) p ) - ((int)q) ) ;
        System.out.println( "swapped values p = " +  ( (char)p) + " q = " + ((char)q) );
    }

The above code swaps 2 chars without using 3rd variable. Here using two variable i.e p & q we have swap the chars

• String Swapping

 
void swappingStrings(String str1, String str2){
        System.out.println( "input value  str1 = " + str1 + "  str2  = " + str2 );
        str2 = str1 + " " + str2;
        String[] split = str2.split(" ");
        str1 = split[1];
        str2 = split[0];
        System.out.println( "swapped values = str1 = " + str1 + " str2 = " + str2);
    }

The above code swaps 2 Strings without using 3rd variable.

Output

Hope this helps.

Java Matrix Multiplication (JMM)

Often in many areas of programming people require a tool which can simplify there n*n matrix multiplication problem in reasonable amount of time.

This can usually be done with 3 tight for loop and special care for handling dimension errors(which i assumes most of you knows) to do this i have a designed a special class and added it to my Utilities framework 1.1.2

Lets quickly take 1 example for 2*2 matrix multiplication using Utilities-1.1.2

  

class MatrixMultiplication
{
public static void main(String[] str) throws DimensionError{
        double[][] a = { {1.2,2.25}, {25.0,28.2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
    }
}
}

Output

So, now you know how simple is matrix multiplication.

Dimension Errors

A special care has been taken to indicate that matrix multiplication is not possible and this is indicated using DimensionError Exception

consider the following example

import math.DimensionError;
import math.Math;
public class MatrixMultiplication {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] str) {
        double[][] a = { {1.2,2.25,2}, {25.0,28.2,2}, {25.2, 14.25,2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
 try{
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
 }catch(DimensionError ex){
  System.out.println(ex.getErrorMessage());
 }
    }
}

Output

Speed

Worst case time complexity is O(n^3)


Download

Huffman-Encoding In Action

Curiosity regarding huffman-decoding process, force me to make one working huffman-encoding/decoding app.

What is Huffman-Encoding In Action ?

Huffman-Encoding In Action is a small GUI program which allows you to visualize how huffman encoding decoding works.

The actual work is done in a class that encapsulates all the functionality, so it should be easy to set up another GUI for it.

For those who don't know what is Huffman Coding read this 

How It Works 

Let q be the priority doubly linked list

l be the list

class Node
{
    Node left, right;
    char data;
    int freq;
    char lEW = ' ';
    char rEW = ' ';
    boolean isRoot = false;
}

Above code is a structure of a node

/**
     * start of the algorithm
     * characters are read'ed 1 by 1 and count is determined using variable count 
     * and a newrec of type node is created which has a data as = char and freq = count for eg:
     * x is the char which appears 3 times then newrec.data = x and newrec.freq = 3 and finally it is inserted 
     * into Sorted DLL and l contains the char x so that when x appear next we could identify that its freq is already
     * determined
     * the same process is repeated for all the char in the string or txt.
     * @param txt 
     */
    public void start( String txt ){
        ogtxt = txt;
        char[] toCharArray = txt.toCharArray();
        for (char x : toCharArray) {
            int count = 0;
            
            
            if( !(l.contains( String.valueOf( x ) ) ) ){
                for (char k : toCharArray) {
                    if( k == x )
                        count++;
                }
                Node newrec = new Node();
                newrec.freq = count;
                newrec.data = x;
                newrec.left = newrec.right = null;
                q.insert(newrec);
                l.add(String.valueOf( x ));
            }
           
        }

        makeSingleTree( );//a recursive function which makes single huffman tree. base case = when there will be only one record in our sorted doubly linked list.
        root = q.delete();// that single tree is now assigned to root
        root.isRoot = true;
         if(root.left != null & root.right != null){
            assignWeights( root );// assigns 0 to every left edge and 1 to every right edge
            traverse(root);//this will traverse and determine the huffman code for each letter or char.
        }else{
            onlyOneNode = true;
        }
        displayHuffmanCode();// this function will display the unique huffman code for each char.
       
    }

So, there you go, now you have basic idea about how the entire process works, the code is well formed in several different methods and is pretty easy to understand as well.

Speed

On my Desktop with with 2.8GHZ. Huffman-Encoder requires just a couple of ms to generate huffman code.

Download

you can download Huffman-Encoding In Action's latest version from here

Miscellaneous 

When given input such as OOOOOOO the encoder will show output Only1Node O 7.

Movie Scheduling Problem

Last night one of mine coding friend thrown a problem on me, & he called it as movie scheduling problem, He wanted me to develop a algo & code for this.

The Problem

Let x be a super-star
Let n be a Producer

n Producers wanted to cast x in there upcoming movie, and for that they are offering the same amount to x but the start & end date interval of each movie making process is different for eg. 1 movie require 10 months to complete whereas other require 1.5 yrs, now the algo. has to decide which movie x will do such that x will make the highest profit.

The criteria for job acceptance is clear: 

x want to make as much money as possible. Because each of these films pays the same fee

per film, this implies x seek the largest possible set of jobs (intervals) such that
no two of them conflict with each other.


I come up with 3 Algo's lets go through it one by one ...

ALGO 1: Earliest Job 1st

Suppose x don't have any work so he will select a movie which ever comes first
but this algo will not make the highest profit bcoz if actor select the 1st movie and the 2nd to 5th movie offers are such that the total time period require to complete all 4 movies is equal to time require to complete 1st movie.
So here the total loss is of 4 movies...


ALGO 2: Smallest Job 1st

This algo is better than the previous one bcoz it will give decent solution.

ALGO 3: Earliest Completion Date

This algo. gives optimal solutions for most of the possible inputs ...

I have coded the solution for Algo 3 whose output looks like ...

The Output
--------------------------------------------------------------------------------------------------------------
The output is a 4 dimension array where
0th column gives movie name
1st column gives start date
2nd column indicates end date
3rd column indicates status P or F , such that P indicate, the no. of movies has to be accepted by x to earn the maxm profit.

Download 

InOrder Traversal Of BST (Iterative Solution)

One best question in my sem-III DSF paper was 

Iterative Solution For Inorder Traversal

I was not prepare for it, but i was knowing the recursive way of traversing the BST tree so i applied  the same concept and find out a algo in 25 minutes sadly in 5 minutes or even less i couldn't complete that question and my ma'am snatch the paper, coz the time was 5:30 pm duhh!!

And after examz i came home and implemented that algo and it was 100% perfect solution for iterative way of Tree traversal , today i m gonna show that to you .......

The thing you must note, in the Stack implementation is that it does not store the data it store the refrence i.e a Node which inturn contains the data.

package datastructurepractice.BST;

/**
 *
 * @author Naved Momin
 */
class StackNode
{
    Node data;
    StackNode next;
}

public class StackForBST {
    StackNode top;
    
    public void push( Node x ){
        if( x != null )
        {
            StackNode newrec = new StackNode();
            newrec.data = x;
            newrec.next = null;
            if( top == null)
                top = newrec;
            else
            {
                newrec.next = top;
                top = newrec;
            }
        }

    }
    
    public void display( ){
        System.out.println( "stack display");
        if( isempty() )
            System.out.println(" empty stack ....");
        StackNode n = top;
        while( n != null){
            Node r = n.data;
            System.out.print (r.data + " ");
            n = n.next;
        }
    }
    
    boolean isempty( ){
        if( top == null)
           return true;
        else
            return false;
    }
    
    Node stacktop( ){
        if( top != null )
        return top.data;
        else
            return null;
    }
            
    
    
    public Node pop( ){
        if( !isempty() ){
            Node x = top.data;
            top = top.next;
            return x;
        }else{
            System.out.println( "stack out of data");
            System.exit(0);
            return null;
        }
    }
    
}


package datastructurepractice.BST;

import java.util.Calendar;
import java.util.Scanner;

/**
 *
 * @author Naved Momin
 */

class Node{
    int data;
    boolean lV = false, rV = false;
    Node left, right;
}
public class BST {
    Node root;
    private long start;
    private long end;
    
    public void travInorder( ){
        inorder(root);
    }
    
    public void insert( int x ){
        Node newrec = new Node();
        newrec.data = x;
        newrec.left = null;
        newrec.right = null;
        if( root == null){
            root = newrec;
        }
        else{
            Node a, b;
            a = b = root;
            while( a != null ){
                b = a;
                if( x < a.data ){
                    a = a.left;
                }else{
                    a = a.right;
                }
            }
            if( x <= b.data ){
                b.left = newrec;
            }else{
                b.right = newrec;
            }
        }
        

    }
    
    public void displayInorder( ){
        System.out.println( "inorder recurssive ");
        long start1 = Calendar.getInstance().getTimeInMillis();
        inorder(root);
        long end1 = Calendar.getInstance().getTimeInMillis();
        System.out.println( "total time taken (Recursive)" + (end1 - start1 ) + " ms");
        
        
        System.out.println( "inorder iterative ");
        start = Calendar.getInstance().getTimeInMillis();
        inOrderIterative(root);
        
        
    }
    
    public void delete( ){
        System.out.println( "enter value ot be deleted");
        int v = new Scanner(System.in).nextInt();
        
        Node a, b ;
        a = b = root;
        while( a != null && a.data != v){
            b = a;
            if( v < a.data )
                a = a.left;
            else
                a = a.right;
        }
        if( a == null )
            System.out.println( "i could not find the value");
        else{
            if( a.left != null && a.right == null){
                if( root == a){
                    root = a.left;
                }else{
                    if( a == b.left){
                        b.left = a.left;
                    }else{
                        b.right = a.left;
                    }
                }
            }
            else if( a.right != null && a.left == null ){
                if( root == a){
                    root = a.right;
                }else if( b.right == a){
                    b.right = a.right;
                }else{
                    b.left = a.right;
                }
            }else if( a.right == null && a.left == null){
                if( root == a){
                    root = null;
                }else if( b.right == a){
                    b.right = null;
                }else{
                    b.left = null;
                }
            }else if( a.right != null && a.left != null){
                Node c = a.right;
                while (c.left != null) {
                    c = c.left;   
                }
                c.left = a.left;
                if( a == root){
                    root = a.right;
                }else {
                    if( b.left == a)
                        b.left = a.right;
                    else
                        b.right = a.right;
                    
                }
                
            }
            System.out.println( "deleted node = " + v) ;
        }
    }
    
    
    
    boolean isempty( ){
        if( root == null)
            return true;
        else
            return false;
    }
    
    public void inOrderIterative( Node root ){
        StackForBST s = new StackForBST();
        s.push(root);
        
        while (true) {            
            Node r = s.stacktop();
           
            while( r.lV && r.rV ){
                s.pop();
                r = s.stacktop();
                
                if( r == null ){
                    end = Calendar.getInstance().getTimeInMillis();
                    System.out.println( "total time taken (Iterative)" + (end - start ) + " ms");
                    System.exit(0);//when stack becomes empty
                }
                    
            }
            
            
            
            if( !r.lV){
                while( r.left != null){
                    r.lV = true;
                    r = r.left;
                    s.push(r);
                }
            }
            r.lV = true;
            System.out.print(r.data + " ");
            
            if( r.lV == true && r.rV == false && r.right != null){
                r.rV = true;
                r = r.right;
                s.push(r);
            }else{
                r.rV = true;
            }
        
       }
        
        
    }
    
    
    
    public void inorder( Node root  ){
       
        if( root != null ){
            inorder(root.left);
            System.out.print( root.data + " ");
            inorder(root.right);
        }
        
    }
    public static void main(String[] args) {
        // TODO code application logic here
    }

}

//Output

run:
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
11111
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
22222
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
333333
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
444444
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
666666
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
555555
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
5656
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
4545
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
2323
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
1212
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
8989
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
45457
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
23235
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
454545
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232345
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
12214
enter 1 for insert 2 for delete 3 for display 4 for exits 
122
exits command executed
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
444
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
55
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
32
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
1
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
2
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
4
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
5
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
6
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
7
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
8
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
9
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
10
enter 1 for insert 2 for delete 3 for display 4 for exits 
3
inorder recurssive 
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666 
total time taken (Recursive)3 ms

inorder iterative 
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666 
total time taken (Iterative)13 ms

From this it looks like recursive approach is faster than iterative approach.......Hence we have proved that recursion is not always slow, there are some problems which are best solved(In terms of performance & simplicity) by "RECURSION".

Trace the code to get the algo. and slight modification will give you preorder & postorder....GL.

Non Restroing Division

/*

 * 4 bit Non Restoring Division implementation

 */


package addandshiftalgo;



import java.util.Scanner;



/**

 *

 * @author Naved Momin

 */

public class NonRestoringDivision {



    int m , q, c, ac;

    String  acStr = "0000", qstr, mstr, cStr, acc, twoscompliment;

  

    private  void read() {

        Scanner s = new Scanner(System.in);

        System.out.println( "enter m " ) ;

        int read = s.nextInt();

        m =  read;

        System.out.println( "enter q " ) ;

        read = s.nextInt();

        q =  read;

        twoscompliment();

    }

  

    void twoscompliment( ){

        twoscompliment = Integer.toBinaryString( - m ).substring(27, 32);

    }

  

    void startALgo( ){

        read();

      

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



            qstr = Integer.toBinaryString(q);

          

            mkQOf4Bit();

            char charAt0 = qstr.charAt(0);

            acStr = Integer.toBinaryString(ac);

            acStr = ( acStr + String.valueOf(charAt0) ).substring(1);

            ac = Integer.parseInt(acStr,2);

            qstr = Integer.toBinaryString(q);

            mkQOf4Bit();

            qstr = qstr.substring(1);

            q = Integer.parseInt(qstr, 2);

            q <<= 1;

            qstr = Integer.toBinaryString(q);

            mkQOf4Bit();

          

            if( c == 1){

                ac = ac + m;

                acStr = Integer.toBinaryString(ac);

                 if( acStr.length() > 5){

                    acStr = acStr.substring(1);

                }

                charAt0 = acStr.charAt(0);

                c = Integer.parseInt(String.valueOf(charAt0), 2);

                if( c == 0 ){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "1";

                    q = Integer.parseInt(qstr, 2);

                }else if( c == 1){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "0";

                    q = Integer.parseInt(qstr, 2);

              

                }

              

                acStr = acStr.substring(1);

              

              

            }else{

                int twoscomp = Integer.parseInt(twoscompliment, 2);

                ac = ac + twoscomp;

                acStr = Integer.toBinaryString(ac);

                if( acStr.length() > 5){

                    acStr = acStr.substring(1);

                }

                      

                charAt0 = acStr.charAt(0);

                c = Integer.parseInt(String.valueOf(charAt0), 2);

                if( c == 1){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "0";

                    q = Integer.parseInt(qstr, 2);

                }else if( c == 0 ){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "1";

                    q = Integer.parseInt(qstr, 2);

                }

              



                acStr = acStr.substring(1);

              

              

            }

          

          

        }

        ac = Integer.parseInt(acStr, 2);

        if( c == 1){

            String  acc = Integer.toBinaryString(c) + acStr;

            int accInt = Integer.parseInt(acc, 2);

            ac = accInt + m;

            acStr = Integer.toBinaryString(ac);

            if( acStr.length() > 5 ){

                acStr = acStr.substring(1);

            }

            ac = Integer.parseInt(acStr, 2);

        }

      

      

        System.out.println( "ac = " + ac + " q = " + q );

      

    }

  

    void mkQOf4Bit( ){

        if( qstr.length() <= 4 ){

                int formula = 4 - qstr.length();

                for (int j = 0; j < formula; j++) {

                    qstr = "0" + qstr;

                }

            }

    }

  

    public static void main(String[] args) {

        // TODO code application logic here

       new NonRestoringDivision().startALgo();

    }

}

Implementation Of Restoring Algorithm

Implementation Of Restoring Algorithm on 4 Bit Numbers

package addandshiftalgo;

import java.util.Scanner;

/**

 *

 * @author Naved Momin<naved.spartans.rocks75@gmail.com>

 */

public class RestoringDivision {

    int m , q, c, ac;

    String  acStr = "0", qstr, mstr, cStr, acc, twoscompliment;

    

    private  void read() {

        Scanner s = new Scanner(System.in);

        System.out.println( "enter m " ) ;

        int read = s.nextInt();

        m =  read;

        System.out.println( "enter q " ) ;

        read = s.nextInt();

        q =  read;

        twoscompliment();

    }

    

    void twoscompliment( ){

        twoscompliment = Integer.toBinaryString( - m ).substring(27, 32);

    }

    

    void startALgo( ){

        read();

        

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

            qstr = Integer.toBinaryString(q);

            

            mkQOf4Bit();

            char charAt0 = qstr.charAt(0);

            acStr = Integer.toBinaryString(ac);

            acStr = acStr + String.valueOf(charAt0);

            ac = Integer.parseInt(acStr,2);

            q <<= 1;

            qstr = Integer.toBinaryString(q);

            if( qstr.length() > 4){

                qstr = qstr.substring(1);

            }else{

                q = Integer.parseInt(qstr, 2);

            }

            

            int n = Integer.parseInt(twoscompliment, 2) ;

            n = n + ac;

            String bString = Integer.toBinaryString(n);

            acStr = bString.substring(1);

            ac = Integer.parseInt(acStr, 2);

            cStr = String.valueOf( acStr.charAt(0) ) ;

            c = Integer.parseInt(cStr,2);

            

            if( c == 1){

                qstr = Integer.toBinaryString(q);

                mkQOf4Bit();

                

                if( qstr.length() > 4 )

                    qstr = qstr.substring(1);

                

                

                

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "0";

                    //qstr = qstr.substring(1);

                    q = Integer.parseInt(qstr,2);

                    String sum = Integer.toBinaryString(c) + Integer.toBinaryString(ac);

                    int s = Integer.parseInt(sum, 2);

                    s = s + m;

                    sum = Integer.toBinaryString(s);

                    ac = Integer.parseInt(sum.substring(1),2);

                    c = 0;

                

            }else{

                qstr = Integer.toBinaryString(q);

                mkQOf4Bit();

                

                if( qstr.length() > 4 )

                    qstr = qstr.substring(1);

                

                

               

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "1";

                    q = Integer.parseInt(qstr,2);

               

                

            }

            

        }

        

        System.out.println( "ac = " + ac + " q = " + q );

        

    }

    

    void mkQOf4Bit( ){

        if( qstr.length() <= 4 ){

                int formula = 4 - qstr.length();

                for (int j = 0; j < formula; j++) {

                    qstr = "0" + qstr;

                }

            }

    }

    

    public static void main(String[] args) {

        // TODO code application logic here

        new RestoringDivision().startALgo();

    }

}

Top 10 Tricks To Fool Your Java Professor

Trick #2

This week's trick will teach you how to find loopholes in existing programs for this you need to have deep understanding about how the underlying code works and how the Platform on which the code is running works.

Let me explain you this with an help of an example:-

Let us consider the simple and very basic example, our challenge is to write code which will tell us whether the given number is odd or not, so lets give a name to this program

ODD OR NOT

when given this challenge most people write this code:

If one can catch the flaw in this code then h/she is a Java Expert

public class OddOrNot
{
 static boolean isOdd(int no){
  return (no % 2) == 1;
 }
 public static void main(String[] arge){
  System.out.println(isOdd(7));
 }
}

Sadly if you are not the one, then i suggest you to read further

There are 2 flaw's in this code 

1. Performance penalty (Mod operations are always less preferable)
2. Code fails as soon as you pass a negative odd number 

Now you know the flaw, then you should be keen to know what best solution can be written for this type of challenges, stay connected....

why code fails ?

This is because, the java's truncating integer division operator[JLS 15.17.2], it implies that when the remainder operation returns a non zero result, it has the same sign as its left operand.  

So now you know the hidden flaw of the above written code, yes it return -1 as soon as you enter any negative odd number.

So, What is the best way to solve this challenge?

USE Bit-Wise-And (&), If you can use bit-wise-and (&) instead of mod (%) operation then always prefer bit-wise-and (&) operation, to increase performance of your application.

public class OddOrNot
{
  static boolean isOdd( int no ){
   return ( no & 1 ) == 1;
  }
  public static void main( String[] arge ){
   System.out.println( isOdd( -7 ) );
  }
}

Working

 If you convert any odd decimal number to its binary equivalent than you will get answer as pattern xxx1 i.e. any odd number ends with 1 and any even number ends with 0 so when we do 1 & 1 = 1 and when we do 0 & 1 = 0

This time you have learned another technique to impress your Boss, friends, professor etc.

Wait for the next trick #3

happy coding

Understanding java.io.StreamCorruptedException: invalid type code: AC

We can transport Objects in Java in two ways

1. Using Serialization 
2. Using RMI ( Remote Method Invocation ) 

last night i was using 1st approach to transport Objects from my server to client, while doing so my code throws 

java.io.StreamCorruptedException: invalid type code: AC

Lets see first what Javadoc has to say about this 

StreamCorruptedException :-  Thrown when control information that was read from an object stream violates internal consistency checks.

 Do you understand any thing ???

No ???

Then, continue reading ...

 So lets look at this exception closely 

This exception (java.io.StreamCorruptedException: invalid type code: AC) only occurs when any one use's a new ObjectOutputStream to write to an existing ObjectInputStream that you have already used a prior ObjectOutputStream to write to. These streams have headers which are written and read by the respective constructors, so if you start another ObjectOutputStream you will write a new header, which starts with - guess what? - 0xAC, and the existing ObjectInputStream isn't expecting another header at this point so it barfs.

So now I guess you have enough understanding about this Exception and next time you will not commit this mistake, and hence this will escape you from wasting enormous amount of time figuring out why this exception is thrown

So the bottom line is

1. Always use only one ObjectOutputStream & corresponding ObjectInputStream through out the life of Socket
2. If you are writing data over Socket using ObjectOutputStream then read that data only using  ObjectInputStream otherwise Exception could be thrown
3. If you want to forget about what you have written then do 

   objectOutputStream.reset();
   

Top 10 Tricks To Fool Your Java Professor

Trick #1

1. Is your java professor always yells at you ? 
2. Does he/she always tells you that you don't know anything about Java ?

If the answer is yes then this post is for you

Its Payback time

Next time when you meet your professor in viva or in general ask him/her a simple question 

Q. can you show me a simple program which print a NUMBER 0123 ?

if your professor is smart enough he/she will write this code 

System.out.println(123);

and gives you a explanation about why he/she has not written 0 (zero) 

if your professor in dumb (which 80% are) will end up with this code

System.out.println(0123);

So, when he will execute this code he will get output as 83

CONFUSED ???

This is because if any number is padded with initial 0 then that number is treated as Octal in Java so when you execute above code the JVM will convert the Octal to Decimal and print 83 on stdout.

So when you will explain this to your professor without the help of Google then he will be impressed :)

The problem is that most people just learn the syntax of a language and not its capability, learning syntax is very easy any moron can learn it within a month or so but learning capability takes almost years of expertise.

Wait for the next trick #2
till that time
stay hungry stay foolish

IO-Utilities

Whenever I take any new project, I always require my Utilities library which provides me following features:

1. Copying my library from dependency to  C Drive or  user's home directory in windows or *nix systems
2. Compressing/Decompressing any Images or files for uploading or transferring it over network
3. Getting extension of any file name in faster way

All this features can be achieved using just one library, and using this library is dam easy...even you can attach a listener to listen the processing i.e.

• Name, count, size, compression level, copying from & copying to path of the file which library is processing ..

To attach a listener use this code

import fileutilslibrary.CopyEvent;
import fileutilslibrary.FileUtils;
import fileutilslibrary.Listener;
import fileutilslibrary.ZipEvent;
import java.io.File;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author Naved Momin<naved.spartans.rocks75@gmail.com>
 */
public class Demo2 implements Listener{

    void start( ) throws IOException{
        FileUtils.getInstance().addListener(this);
     
        FileUtils.zipMyFolder(new File("C:\\Users\\Admin\\Desktop\\imgToVideo/RemoteDesktop"),
                  new File("C:/Users/Admin/Desktop/HMS Latest/RDnew.zip"),9);
                 

     
    }
    public static void main(String[] args) {
 
        try {
            // TODO code application logic here
            new Demo2().start();
        } catch (IOException ex) {
            Logger.getLogger(Demo2.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    @Override
    public void copyListener(CopyEvent e) {
        //notification about copying event
    }

    @Override
    public void zipListener(ZipEvent e) {
        //notification about zip event
        System.out.println( "name " +e.getZipingFileName() +  "\n" + "size " + e.getZipingFileSize() + "\n" +
        " count " + e.getFileCount( ) + "\n" +
        "level  " + e.getCompressionLevel() );
    }
}

Various Methods:-

Copy a Directory

FileUtils.copyDirectory(src, dest);

Copy a File

FileUtils.copyFile(src, dest);

Zip Directory 

FileUtils.zipMyFolder(src, dest);

Zip Directory With Custom Compression Level

FileUtils.zipMyFolder(src, dest, compressionLevel);

Note: Compression level must be between 0-9, by default 0 is used

Zip File

FileUtils.zipMyFile(src, dest);

Zip File With Custom Compression Level

FileUtils.zipMyFile(src, dest, compressionLevel);

Note: Compression level must be between 0-9, by default 0 is used

UnZip File

FileUtils.doUnZip(src, dest);

Get File Extension (10x faster)

FileUtils.getExtension(path);

Reverse a String

FileUtils.reverse(str);

Get File Name 

FileUtils.getName(pathToFile);

Note: The library is written in pure Java code except the Wallpaper class which throws NotSupportedOSException if OS is not supported by the library for more information see Javadoc included in the download package.

This library is totally compatible with various 3rd party zip utilities like winrar, which means you can zip your files programmatically and still use winrar for unzip'ing the file or vice-versa is also possible. 

For any bug or suggestions mail me at naved.spartans.rocks75@gmail.com

This Library is License under GNU General Public License

Download latest builds

Take Away ( Free Of Cost )

This week on take away i m giving away a software which i had sole'd to 4 peoples, 1 last year and 3 this year as a final year project (diploma),  The software performs following functions

1. Encrypt any of your .png or .jpg files with AES (  Advanced Encryption Standard  )

Last year when i sole'd this project that guy asked me a smart question 

What if there is a spyware running on my computer which is capturing all my input or keystroke's ?

 So to solve this problem i have added a layer called second factor of authentication which is

SOMETHING YOU HAVE

now the software can defeat any keylogger's (remember keylogger's have types)

1. The ones which only capture your keystokes
2. another one is a bit advance and apart form capturing keystroke's they also capture your screen

So now even though that spyware software has your secret key which you have used to encrypt your image's, he/she will not be able to decrypt it until he/she has your "TOKEN"

TOKEN can be any thing your pen-drive, external hdd, or whatever which you can plug into system and prove that you are the one which actually encrypted the images, unless & until token has not been inserted the software will not perform decryption process.

So i m giving away the simple version of this software which only encrypts and decrypts without defeating keylogger's .

if you want the more advance version of this software then mail me at naved.spartans.rocks75@gmail.com

Always download latest builds