Compute 'x' raised to power 'n' in O(logN) time using Java

Hello friends,

In  continuation to the recursive algorithms, I am here with you with another problem.

Suppose we have a number 'x' a another positive Integer 'n'. We need to find the value of 'x' raised to power to 'n'.

Friends please find below the code in java for this.

package com.recursion.power;

import java.util.Scanner;

/**
*
* @author krishna.k
*
*         This class computes the value of 'x' raised to power of 'n' in time
*         complexity of O(log n). 'x' is Integer, and n is a positive Integer
*         including 0.
*
*
*
*
*/
public class PowerComputation {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the value of x (base)");
        int x = sc.nextInt();
        System.out.println("Enter a positve integer n (power)");
        int n = sc.nextInt();
        System.out.println("Value of " + x + " raised to power " + n + " is " + computePower(x, n));
    }

    public static int computePower(int x, int n) {
        if (x == 0 || x == 1 || n == 1) {
            return x;
        }
        if (n == 0) {
            return 1;
        }
        int temp = computePower(x, n / 2);
        if (n % 2 == 0) {
            return temp * temp;
        } else {
            return x * temp * temp;
        }
    }
}

Print the elements of the array in straight order and in reverse order using Recursion in Java

Hello friends,

I am here with another question in continuation to our simple recursive algorithm based questions.

If we have an array of numbers, we need to print the elements of the array in straight order and in reverse order. 

We can easily do this using iteration but for learning purpose lets try doing this using recursion.

Note that to print the elements in the reverse order I have used two methods, one uses simple index based manipulation but lets observe the other method : printReverseInterestingWay(). While other method prints the elements as it visits the element first time but this method prints the element during re-visit (following the recurrence method calls in stack)

Friends Please find the code below.

package com.recursion.printarray;

public class StraightReversePrintArray {
    public static void main(String[] args) {
        int[] input = { 1, 2, 3, 4, 6, 8 };
        int size = input.length;
        System.out.println("Straight printing of the Array: ");
        printStraight(input, size, 0);
        System.out.println("Reverse printing of the Array: ");
        printReverse(input, size, 0);
        System.out.println("Reverse printing of the Array using interesting way: ");
        printReverseInterestingWay(input, size, 0);
    }

    public static void printStraight(int[] input, int size, int i) {
        if(i < size){
            System.out.println(input[i]);
            printStraight(input, size, i+1);
        }
    }

    public static void printReverse(int[] input, int size, int i) {
        if(i < size){
            System.out.println(input[size-i-1]);
            printReverse(input, size, i+1);
        }
    }
    
    public static void printReverseInterestingWay(int[] input, int size, int i){
        if(i < size){
            printReverseInterestingWay(input, size, i+1);
            System.out.println(input[i]);
        }
    }
}

Sum of first N natural numbers by recursion in Java

Dear Friends,

I am here with you with another simple problem.

If we have a natural number, N then we need to find the sum of first N natural numbers.

This has a simple solution which can be simply printing the value of N*(N+1)/2. For learning purpose lets try this problem using recursion. Friends please find below the code using recursion.

package com.recursion.sum.numbers;

import java.util.Scanner;

/**
 * This can be solved using simple formula for sum of first n natural numbers
 * but for learning purpose we are solving it using Recursion
 * 
 * @author krishna.k
 *
 */
public class SumOfFirstNNumbers {
    public static void main(String[] args) {
        System.out.println("Enter the Number");
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        System.out.println("Sum of first "+ number+" numbers is "+computeSum(number));
    }

    public static int computeSum(int number) {
        if(number == 1){
            return 1;
        }
        return number + computeSum(number-1);
    }
}

Sum of digits of a number N using recursion in Java

Hello friends,

I am here with you with an easy problem.

Given a number N , we need to output the sum of the digits of the number N.

This can be solved using iteration but for learning purpose lets do it using recursion.

Friends, please find the code below for this problem.

package com.recursion.sumofdigits;

import java.util.Scanner;

public class SumOfDigitsOfNumN {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the Number: ");
        int number = sc.nextInt();
        System.out.println("Sum of digits is "+getSum(number));
    }
    
    public static int getSum(int number){
        int lsd = number%10; // least significant digit
        int remainingNum = number/10;
        if(remainingNum == 0){
            return lsd;
        }
        return lsd+getSum(remainingNum);
    }
}

Detecting if a binary tree is a Binary Seach Tree: Java implementation

Hello Friends,

Today I am with you with another algorithm. Its about detecting if a Binary tree is a BST or not. A regular binary tree is a tree for which each node has number of children equal to 0, 1 or 2. A binary search tree has same properties as of regular binary tree with an additional property according to which any node has data  smaller than the data in its right child and greater data than the data in its left child.


We have two binary trees below.







Friends Lets look at the Java implementation solving this problem statement.

[Note that tree[] holds actual tree node values, left[] holds the index in tree[] corresponding to the left child of the each index and right[] holds the index in tree[] corresponding to the right child of the each index]

public class BSTDetector {
    // tree holds actual tree node values
    Integer tree[];
    // holds the index in tree[] corresponding to the left child of the each index
    Integer left[];
    // holds the index in tree[] corresponding to the right child of the each index
    Integer right[];

    public boolean isBinaryTreeBST(Integer tree[], Integer left[], Integer right[]) {
        this.tree = tree;
        this.left = left;
        this.right = right;
        return detectBST(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
    }

    private boolean detectBST(int leftRange, int rightRange, int currentIndex) {
        boolean isLeftChildvalid = true;
        boolean isRightChildValid = true;
        if (left[currentIndex] != null) {
            isLeftChildvalid = tree[currentIndex] >= tree[left[currentIndex]];
        }
        if (right[currentIndex] != null) {
            isRightChildValid = tree[currentIndex] <= tree[right[currentIndex]];
        }
        boolean isInRange = leftRange <= tree[currentIndex] && tree[currentIndex] <= rightRange;
        if (!isRightChildValid || !isLeftChildvalid || !isInRange) {
            return false;
        }
        boolean isLeftTreeBST = true;
        boolean isRightTreeBST = true;
        if (left[currentIndex] != null) {
            isLeftTreeBST = detectBST(leftRange, tree[currentIndex], left[currentIndex]);
        }
        if (right[currentIndex] != null) {
            isRightTreeBST = detectBST(tree[currentIndex], rightRange, right[currentIndex]);
        }

        return isLeftTreeBST && isRightTreeBST;
    }

    public static void main(String[] args) {
        Integer tree[] = { 10, 8, 6, 22, 12, 14 };
        Integer left[] = { 1, null, null, null, null, 2 };
        Integer right[] = { 4, null, null, null, 5, 3 };
        BSTDetector bstDetector = new BSTDetector();
        boolean isBST = bstDetector.isBinaryTreeBST(tree, left, right);
        System.out.println(isBST);

        Integer anotherInputTree[] = { 10, 8, 14, 22, 12, 15 };
        Integer anotherInputLeft[] = { 1, null, null, null, null, 2 };
        Integer anotherInputRight[] = { 4, null, null, null, 5, 3 };
        isBST = bstDetector.isBinaryTreeBST(anotherInputTree, anotherInputLeft, anotherInputRight);
        System.out.println(isBST);
    }
}

 

Root to Leaf Sum in a Binary tree : java Implementation

Hello friends,

Suppose we have a binary tree (not necessary a binary search tree), whose each node represent an Integer. We have a number: SUM. We need to find if there exist a path from Root to any Leaf such that sum of all the nodes equals the SUM. The path should contain full path from Root to a Leaf node.



If we have a binary tree as above and SUM as 26 then the Valid path comprises of (11,5,10) and not 10 and 16 as 10 and 16 is not a complete path from root to leaf but (11,5,10) nodes create a path from root (10) to leaf (11).


Friends, please find below the java code solving this problem. Please note that for representing the binary tree three arrays have been used. :
1. tree[] : This holds the actual values of the tree. This is 0 indexed array.
2. left[] : This  holds index of left child for the current index.
3. right[] : This holds index of right child for the current index.

public class RootToLeafSumInBinaryTree {
    
    // tree holds actual tree node values
    static Integer tree[] = { 10, 16, 5, -3, 6, 11 };
    // holds the index in tree[] corresponding to the left child of the each index
    static Integer left[] = { 1, null, 4, null, null, null };
    // holds the index in tree[] corresponding to the right child of the each index
    static Integer right[] = { 2, 3, 5, null, null, null };
    static Integer result[] = new Integer[tree.length];
    static int resultIndex = 0;

    public static void main(String[] args) {

        Integer sum = 21;
        boolean isSuccess = rootToSum(0, sum);
        for (int i = 0; isSuccess &&  i < resultIndex; i++) {
            System.out.println(result[i]);
        }
    }

    public static boolean rootToSum(int currentIndex, Integer sum) {
        if (left[currentIndex] == null && right[currentIndex] == null) {
            if (sum - tree[currentIndex] == 0) {
                result[resultIndex++] = tree[currentIndex];
                return true;
            } else {
                return false;
            }
        }
        boolean isLeftSuccess = false;
        boolean isRightSuccess = false;
        sum = sum - tree[currentIndex];
        if (left[currentIndex] != null) {
            isLeftSuccess = rootToSum(left[currentIndex], sum);
        }
        if (right[currentIndex] != null) {
            isRightSuccess = rootToSum(right[currentIndex], sum);
        }
        // be careful here we need to see if we get success from Either of Left
        // or Right branch we need to return Success as we have a path where the
        // sum is equal to the provided sum. 
        if (isLeftSuccess || isRightSuccess) {
            result[resultIndex++] = tree[currentIndex];
            return true;
        }
        return false;
    }
}

 

Topologial sort : Java Implementation

Hello Friends,

I am here with you with another algorithm. Its Topological sorting of a directed graph. Suppose we have few tasks which are interdependent. Lets represent this system in a graph. Each task is represented by a Vertex and will be connected to the Vertices with which it has dependency relation. All Vertices connected to a Vertex V with INCOMING edges on V will be the vertices on  which  Vertex V is dependent upon. So all the tasks represented by the such vertices should be performed before task represented by Vertex V is completed.


A such system represented as graph is as below :





Here for example Before task represented by C is performed , Tasks represented by  A and B must be performed as C has dependency on A and B.

Friends Please find below the code for the same. I have used my own custom HashMap and Stack for its implementation, so you can see a basic internal working of HashMap and Stack also.

public class TopologicalSort {

    public static class Graph {
        int maxSize;
        int size;
        Vertex vertices[];
        HashMap map;
        Stack stack;

        public Graph(int maxSize) {
            this.maxSize = maxSize;
            vertices = new Vertex[maxSize];
            map = new HashMap();
            stack = new Stack(maxSize);
        }

        public static class Vertex {
            char name;
            Neighbour adj;
            State state = State.NEW;

            public Vertex(char name) {
                this.name = name;
            }
        }

        public enum State {
            NEW, INPROGRESS, VISITED
        }

        public static class Neighbour {
            Vertex vertex;
            Neighbour next;

            public Neighbour(Vertex vertex, Neighbour next) {
                this.vertex = vertex;
                this.next = next;
            }
        }

        public void invokeTopologicalSorting() {
            for (int i = 0; i < maxSize; i++) {
                exploreVertex(vertices[i]);
            }
            for (int i = 0; !stack.isEmpty(); i++) {
                System.out.println(stack.pop().name);
            }
        }

        /**
         * 
         * The basic idea in this method is to fully explore the vertex, and
         * check if its any Neighbor has been left un explored, if so then need
         * to explore the Neighbor by recursive call to this method. After fully
         * exploring we need to add the vertex to the stack. Thus first the
         * leaves will be pushed to the stack and then when the vertex is re
         * visited by recurrence stack then we see if there are any more
         * neighbor left un explored , if so we need to repeat the process else
         * we come out of the while loop and push the explored vertex in the
         * stack.
         * 
         * Point to note here is: A vertex if considered a Task has dependencies
         * on the vertices which are connected to it by In-coming edges. So for
         * any Vertex, V we need to explore its neighbor first so that they are
         * pushed to the stack first (and will be popped after the current
         * vertex, V).
         */
        public void exploreVertex(Vertex v) {
            if (v.state != State.VISITED) {
                v.state = State.VISITED;
                Neighbour adj = v.adj;
                while (adj != null) {
                    Vertex neighbour = adj.vertex;
                    if (neighbour.state != State.VISITED) {
                        exploreVertex(adj.vertex);
                    }
                    adj = adj.next;
                }
                stack.push(v);
            }
        }

        public void addVertex(char name) {
            vertices[size++] = new Vertex(name);
            map.put(name, vertices[size - 1]);
        }

        public void addNeighbour(char source, char destination) {
            Vertex sourceV = map.get(source);
            Vertex destinationV = map.get(destination);
            sourceV.adj = new Neighbour(destinationV, sourceV.adj);
        }

        public static class Stack {
            Vertex[] stack;
            int maxSize;
            int top = -1;

            public Stack(int maxSize) {
                this.maxSize = maxSize;
                stack = new Vertex[maxSize];
            }

            public void push(Vertex u) {
                stack[++top] = u;
            }

            public Vertex pop() {
                Vertex v = stack[top];
                stack[top] = null;
                top--;
                return v;
            }

            public boolean isEmpty() {
                return top == -1;
            }
        }

        public static class HashMap {
            int prime = 499;
            MapNode[] map = new MapNode[prime];

            public static class MapNode {
                char key;
                Vertex value;
                MapNode next;

                MapNode(char key, Vertex value, MapNode next) {
                    this.key = key;
                    this.value = value;
                    this.next = next;
                }
            }

            public int index(char key) {
                return hashcode(key) % prime;
            }

            public int hashcode(char key) {
                return 31 * key;
            }

            public boolean put(char key, Vertex value) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return false;
                    }
                    temp = temp.next;
                }
                map[index] = new MapNode(key, value, map[index]);
                return true;
            }

            public Vertex get(char key) {
                int index = index(key);
                MapNode temp = map[index];
                while (temp != null) {
                    if (temp.key == key) {
                        return temp.value;
                    }
                    temp = temp.next;
                }
                return null;
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addVertex('F');
        graph.addVertex('G');
        graph.addVertex('H');
        graph.addNeighbour('A', 'C');
        graph.addNeighbour('B', 'C');
        graph.addNeighbour('B', 'D');
        graph.addNeighbour('C', 'E');
        graph.addNeighbour('D', 'F');
        graph.addNeighbour('E', 'F');
        graph.addNeighbour('E', 'H');
        graph.addNeighbour('F', 'G');
        graph.invokeTopologicalSorting();
    }
}