Monday, January 26, 2015

Segment Tree (for finding sum of given range) Implementation : Java

Tutorial : http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

If the array has N elements.
Then segment tree array has total = 2*N-1 elements.

Number of internal nodes = N-1;


Since we are using array to represent the relations there may be cases when the tree's leaf elements are not all at the maximum depth. If we don't allocate these indices, we'll be getting incorrect results and possible null pointer exceptions. To maintain the tree structure, we must allocate space for missing children as well.



Total space to be allocated thus becomes

    2*(int)Math.pow(2, height)-1;  (and NOT just 2*N-1)

where

Height of segment tree = (int)Math.ceil(Math.log(N)/Math.log(2));

Source:

import java.util.*;

public class SegmentTree {
    private static int[] st;
    
    //Construction of Segment Tree
    public static int[] constructSegmentTree(int[] arr){
        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
        int size = 2*(int)Math.pow(2, height)-1; 
        st = new int[size];
        constructST(arr, 0, arr.length-1, 0);
        return st;
    }
    
    public static int constructST(int[] arr, int ss, int se, int si){
        if(ss==se){
            st[si] = arr[ss];
            return st[si];
        }
        int mid = ss+(se-ss)/2;
        st[si] = constructST(arr, ss, mid, si*2+1)+
                 constructST(arr, mid+1, se, si*2+2);
        return st[si];
    }
    
    //Finding The sum of given Range
    public static int findRangeSum(int ss, int se, int[] arr){
        int n = arr.length;
        if(ss<0 || se > n-1 || ss>se){
            throw new IllegalArgumentException("Invalid arguments");
        }
        return findSum(0, n-1, ss, se, 0);
    }
    
    public static int findSum(int ss, int se, int qs, int qe, int si){ 
        if(ss>qe || se < qs)return 0;
        if(qs<=ss && qe>=se)return st[si];
        
        int mid = ss+(se-ss)/2;
        return findSum(ss, mid, qs, qe, si*2+1)+
               findSum(mid+1, se, qs, qe, si*2+2);
    }
    
    //Updating a particular index's value
    static void updateValue(int arr[], int i, int newVal){
        if(i<0 || i>arr.length-1)throw new IllegalArgumentException();
        int difference = newVal - arr[i];
        arr[i] = newVal;
        updValue(arr, 0, arr.length-1, i, difference, 0);
    }
    
    static void updValue(int[] arr, int ss, int se, int i, int difference, int si){
        if(i< ss || i>se)return;
        st[si] = st[si]+difference;
        if(ss!=se){
            int mid = ss+(se-ss)/2;
            updValue(arr, ss, mid, i, difference, si*2+1);
            updValue(arr, mid+1, se, i, difference, si*2+2);
        }
    } 
    
    public static void main(String[] args) throws Exception{ 
            int[] arr = {1,3,5,7,9,11};
            System.out.println("Height = "+(int)Math.ceil(Math.log(arr.length)/Math.log(2)));
            constructSegmentTree(arr);
            System.out.println("Values array = "+Arrays.toString(arr));
            System.out.println("Segement Tree array = "+Arrays.toString(st));
            System.out.println("Range sum from index 2 to index 4 = "+findRangeSum(2, 4, arr));
            
            //Update value
            updateValue(arr, 2, 2);
            System.out.println("Updated value at index 2 in the original array to "+2);
            System.out.println("Range sum from index 0 to index 2 = "+findRangeSum(0, 2, arr));
    } 
}

Output:

Height = 3
Values array = [1, 3, 5, 7, 9, 11]
Segement Tree array = [36, 9, 27, 4, 5, 16, 11, 1, 3, 0, 0, 7, 9, 0, 0]
Range sum from index 2 to index 4 = 21
Updated value at index 2 in the original array to 2
Range sum from index 0 to index 2 = 6

Sunday, January 25, 2015

Euclid's Algorithm for Calculating GCD of two Integers [Java Implementation]

Tutorial on the Algorithm : http://www.rit.edu/~w-asc/documents/services/resources/handouts/DM%20-%206%20Euclidean%20Algorithm.pdf

Source:

public class EuclidGCD {
    public static int findGCD(int a, int b){  
        if(a==0)return b;
        if(b==0)return a;
        
        if(a<0)a=-a;
        if(b<0)b=-b;
        
        int min = Math.min(a, b);
        int max = a;
        if(min==a)max = b;
       
        int t, rem = t = min;
        
        while(t!=0){
            rem = t;
            t = max%min; 
            max = min;
            min = t; 
        }
        return rem;
    }
    
    public static void main(String[] args) throws Exception{ 
        System.out.println(findGCD(4278, 8602));
    } 
}

Output:

46

Monday, January 5, 2015

Fast Ranged Prime Number Generation using Segmented sieve of Eratosthenes

Implementation of Segmented sieve of Eratosthenes.

Source:

import java.util.*;

class SSOE{

    public static ArrayList<Integer> getPrimes(int sqrt) {
        int q = sqrt;
        ArrayList<Integer> primes = new ArrayList<>();
        if (q < 2) {
            return primes;
        }
        if (q % 2 == 0) {
            q--;
        }
        boolean check[] = new boolean[q + 1];
        for (int i = 3; i <= check.length - 1; i += 2) {
            check[i] = true;
        }
        for (int i = 1; i <= check.length - 1; i += 2) {
            if (check[i]) {
                primes.add(i);
                for (int j = i * i; j <= check.length - 1; j += i) {
                    check[j] = false;
                }
            }
        }
        return primes;
    }

    static List<Integer> getPrimes(int p, int q) {
        ArrayList<Integer> primeList = new ArrayList<>();
        if (p <= 2) {
            if (q >= 2) {
                primeList.add(2);
            }
            p = 3;
        }
        if (p % 2 == 0) {
            p++;
        }
        if (q % 2 == 0) {
            q--;
        }
        if (q >= p) {

            int sqrt = (int) Math.sqrt(q);
            ArrayList<Integer> primes = getPrimes(sqrt);
            boolean check[] = new boolean[q - p + 1];
            for (int i = 0; i <= check.length - 1; i += 2) {
                check[i] = true;
            }
            for (int prime : primes) {
                int index, rem = p % prime;
                if (rem == 0) {
                    index = rem;
                } else {
                    index = prime - rem;
                }
                if (index + p != prime && index < check.length) {
                    check[index] = false;
                } else {
                    index += prime;
                }
                while (index <= check.length - 1) {
                    check[index] = false;
                    index += prime;
                }
            }

            for (int i = 0; i <= check.length - 1; ++i) {
                if (check[i]) {
                    primeList.add(i + p);
                }
            }
        }
        return primeList;
    }

    public static void main(String[] args) throws Exception {
        System.out.println(getPrimes(1, 100));
    }
}

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Friday, January 2, 2015

Inserting a number's bits into another 32 bit number at a specified position. [Java]

Q. You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.

EXAMPLE

Input:    N = 10000000000, M = 10011, i = 2, j = 6
Output:   N = 10001001100

Source:

public class Code{
    static int change(int N, int M, int i, int j){
        return ((~(-1>>>(31-(j-i))<<i))&N)|(M<<i);
    }
    
    public static void main(String[] args){  
        int N = (int)Long.parseLong("10110011001100111111001111111100", 2);
        int M = Integer.parseInt("110011", 2); 
        System.out.println(Integer.toBinaryString(change(N, M, 17, 22)));
        
        N = Integer.parseInt("10000000000", 2);
        M = Integer.parseInt("10011", 2);
        System.out.println(Integer.toBinaryString(change(N, M, 2, 6)));
    }
}

Output:

10110011011001111111001111111100
10001001100

Bit Manipulation in Java

The >> Operator (Shifts bits right. Inserts duplicate bits of the bit initially at the Most Significant Position)

#1

10000000 00000000 00000000 00001000 >> 3 

=

11110000 00000000 00000000 00000001

#2

00000000 00000000 00000000 00001000 >> 3

=

00000000 00000000 00000000 00000001

The >>> Operator (Shifts bits right. Inserts 0s at the left)

#1

10000000 00000000 00000000 00001000 >>> 3

=

00010000 00000000 00000000 00000001

#2

00000000 00000000 00000000 00001000 >>> 3

=

00000000 00000000 00000000 00000001

There is no <<< Operator (that'd be useless)

The << Operator (Shifts bits left, inserts 0s at the right)

#1

10000000 00000000 00000000 00001000 << 3

=

00000000 00000000 00000000 10000000

#2

10000000 00000000 00000000 00010001 << 3

=

00000000 00000000 00000000 01001000

For working with these 32 bit binary string representations, use

int A = (int)Long.parseLong("10000000000000000000000000001001", 2);

#Note

int A = (int)Long.parseLong("10000000000000000000000000001001", 2); 
        System.out.println(Integer.toBinaryString(A));
int A = Integer.parseInt(   "-0000000000000000000000000001001", 2);
        System.out.println(Integer.toBinaryString(A));

Output:

10000000000000000000000000001001
11111111111111111111111111110111

These are different because the '-' sign does not just set the 32nd bit to 1. It takes the two's complement of the number represented by the rest of the string and then puts a 1 bit at the 32nd position.

Two's complement is calculated by inverting bits and adding 1. (One's complement + Add 1)

                 11000 
inverted bits =  00111
                +    1 
                 01000

So in the second case,

          0000000000000000000000000001001 (31 bits)
invert =  1111111111111111111111111110110 
                                       +1
          1111111111111111111111111110111  

So the output is 
         11111111111111111111111111110111 (32 bits)

Thursday, January 1, 2015

An algorithm to print all paths which sum to a given value in a Binary Tree.

Q. You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.

Algorithm:

1. Start at the root or any other node (if a node other than root is given).
2. Check all nodes to left and to right recursively, pass the running sum and a string representation of the path downwards.
3. If the sum equals the required value, store that path or print it.
4. Continue down until you hit a null. (We don't quit when running sum matches the required value as there may be negative value nodes down in the path and then a positive one or there maybe zero value nodes down in the tree which IS a possible path).

Source:

import java.util.ArrayList;
import java.util.List;

class Code{
    class Node{ 
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return Integer.toString(value);
        } 
    }
    
    Node root;
    
    void helper(List<String> list, String s, Node origin, int sum, int value){
        if(origin == null)return;
        sum+=origin.value;
        if(sum==value){String add = s;add+=" "+origin.toString(); list.add(add);} 
        helper(list, s+" "+origin.toString(), origin.left, sum, value);
        helper(list, s+" "+origin.toString(), origin.right, sum ,value);   
    }
    
    void checkPaths(Node root, List<String> list, int value){ 
        if(root == null)return;  
        helper(list,"", root, 0, value);   
        checkPaths(root.left, list, value);
        checkPaths(root.right, list, value); 
    }
    
    public void printPathsForValue(int value){
        List<String> paths = new ArrayList<>();
        checkPaths(root, paths, value);
        System.out.println("Paths: \n"+paths);
    }
    
    public void buildCustomTree(){
        root = new Node(1);
        setChildren(root, 2, 3);
        setChildren(root.left, 1, 2);
        setChildren(root.left.right, null, 3);   
        setChildren(root.right, 1, 3); 
        setChildren(root.right.left, null, 4);
        setChildren(root.right.right, null, 2);
        setChildren(root.right.right.right, 1, null);
        
        root = new Node(1);
        setChildren(root, 2, 3);
        setChildren(root.left, 1, 0);
        setChildren(root.right, 1, 0);
        setChildren(root.left.right, 0, 1);
        setChildren(root.right, 1, 0);
        setChildren(root.left.right, 0, 1);
        setChildren(root.left.right.left, 1, null);
        setChildren(root.right.left, 3, 2);
        setChildren(root.right.left.right, 1, null);
        
        //with -ve values as well
        root = new Node(1);
        setChildren(root, 2, 3);
        setChildren(root.left, 1, 0);
        setChildren(root.left.left, -1, null);
        setChildren(root.left.left.left, 1, 2);
        setChildren(root.left.left.left.right, -1, null); 
        setChildren(root.left.right, 0, 1);
        setChildren(root.left.right.left, null, 1);
        setChildren(root.right, 1, 0);
        setChildren(root.right.left, 3, 2);
        setChildren(root.right.left.right, 1, null);
    }
    
    private void setChildren(Node node, Integer left, Integer right){
        if(left!=null)node.left = new Node(left);
        if(right!=null)node.right = new Node(right);
    }
    
    public static void main(String[] args){
        Code tree = new Code(); 
        tree.buildCustomTree();
        tree.printPathsForValue(4);
    }
}

Output:

Paths:
[ 1 2 1,  1 2 1 -1 1,  1 2 1 -1 2 -1,  1 2 0 0 1,  1 2 0 1,  1 3,  1 3 0,  2 1 -1 2,  3 1,  1 3,  1 2 1]

Checking if a given binary tree is a sub-tree of another binary tree.

Q. You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

Algorithm:

1. Traverse T1, find nodes that match the root of T2.
2. For all the nodes that match, check if the trees with those roots are equivalent. 

Source:

import java.util.ArrayList;
import java.util.List;

class Code{
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
        
        @Override
        public boolean equals(Object o){
            return o.hashCode() == this.hashCode();
        }

        @Override
        public int hashCode() {
            return value;
        } 
    }
    
    private void getIdenticals(Node node, Node B, List<Node> store){
        if(node==null) return;
        if(node.equals(B)) store.add(node);
        getIdenticals(node.left, B, store);
        getIdenticals(node.right, B, store); 
    }
    
    public boolean isSubtree(Node root, Node B){ 
        if(root == null || B == null)return false;
        List<Node> possibleNodes = new ArrayList<>();
        getIdenticals(root, B, possibleNodes);
        for(Node n:possibleNodes)
            if(match(n, B))return true;
        return false;
    }
    
    private boolean match(Node head, Node B){
        if(head==null && B == null)return true;
        if(head==null || B == null)return false;
        if(head.equals(B)){
            if(match(head.left, B.left) && match(head.right, B.right)) return true;
        }
        return false;
    }
    
    Node root;
    Node A, B;
    
    public void buildCustomTree(){
        A = root = new Node(5);
        setChildren(root, 7, 6);
        setChildren(root.left, 8, 10);
        setChildren(root.left.right, 12, 13);
        setChildren(root.left.right.left, 14, null);
        setChildren(root.left.right.right, null, 15);
        setChildren(root.left.right.right.right, 16, 17);
        setChildren(root.left.right.right.right.left, null, 18);
        setChildren(root.right, null, 11);
        
        B = new Node(13);
        setChildren(B, null, 15);
        setChildren(B.right, 16, 17);
        setChildren(B.right.left, null, 18); 
    }
    
    private void setChildren(Node node, Integer left, Integer right){
        if(left!=null)node.left = new Node(left);
        if(right!=null)node.right = new Node(right);
    }
    
    public static void main(String[] args){
        Code tree = new Code();
        tree.buildCustomTree();
        System.out.println(tree.isSubtree(tree.A, tree.B));
    }
}

Output:

true