SPOJ Prime Generator Solution in Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        SieveOfEratosthenes soe = new SieveOfEratosthenes(SieveOfEratosthenes.LIMIT);

        int T = in.nextInt();
        while (T-- != 0) {
            int m = in.nextInt();
            int n = in.nextInt();
            if (n < SieveOfEratosthenes.LIMIT) {
                for (int i = m; i <= n; i++) {
                    if (soe.isPrime(i)) {
                        System.out.println(i);
                    }
                }
            } else {

                // primes which are lesser than the square root of n, since the
                // max prime factor of n will be less than or equal to square root of n
                List<Integer> primes = soe.getPrimes((int) Math.sqrt(n));

                boolean[] a = new boolean[n - m + 1];
                for (int i = 0; i < a.length; i++) {
                    a[i] = true;
                }

                // Similar to sieve of eratosthenes, fill the boolean
                // array with the divisibility with prime factors
                for (int prime : primes) {
                    int div = m / prime;
                    if (div * prime == m) {
                        a[0] = false;
                    } else {
                        div += 1;
                    }
                    for (int i = div * prime; i <= n; i += prime) {
                        if (i >= m && i <= n) {
                            a[i - m] = false;
                        }

                    }
                }

                for (int i = 0; i < a.length; i++) {
                    if (a[i]) {
                        System.out.println(m + i);
                    }
                }
            }
            System.out.println();
        }
    }

    public static class SieveOfEratosthenes {

        public static final int LIMIT = 10000000;

        private boolean[] a;

        public SieveOfEratosthenes(int N) {
            a = new boolean[N + 1];
            for (int i = 0; i < N; i++) {
                a[i] = true;
            }
            a[0] = false;
            a[1] = false;

            int root = (int) Math.sqrt(N);
            for (int i = 2; i <= root; i++) {
                for (int j = 2 * i; j <= N; j += i) {
                    a[j] = false;
                }
            }
        }

        public boolean isPrime(int n) {
            return a[n];
        }

        public List<Integer> getPrimes() {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 1; i < a.length; i++) {
                if (a[i]) {
                    list.add(i);
                }
            }
            return list;
        }

        public List<Integer> getPrimes(int n) {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 1; i <= n; i++) {
                if (a[i]) {
                    list.add(i);
                }
            }
            return list;
        }
    }

    public static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Sample Input:

2
1 10
3 5

Sample Output:

2
3
5
7

3
5

Segment Tree Implementation in Java

Segment tree is just another binary tree which supporting operations such as finding the minimum, maximum or sum of a given range of index in the array. The tree implementation is similar to the binary tree implementation of heap over an array.

Based on the requirements the current code for range minimum query can be modified for the range maximum query or range sum query.

The api for the given class looks like:

public class SegmentTree {
    public SegmentTree(int[] A);
    public int query(Point interval);
    public void update(int index, int value);
}

Complete Code:

import java.awt.*;

/**
 * Created by dhruv.pancholi on 17/01/16.
 * @author Dhruv Pancholi
 * @version 1.0
 */
public class SegmentTree {

    private int[] oArray;
    private int[] stArray;

    /**
     * Class which builds segment tree for the input array
     *
     * @param oArray original array
     */
    public SegmentTree(int[] oArray) {
        this.oArray = oArray;

        // The required length of the segment tree array
        // same as heap array
        int len = (int) Math.pow(2, Math.ceil(log2(oArray.length) + 1));
        stArray = new int[len];

        buildSegmentTree(0, new Point(0, oArray.length - 1));
    }

    /**
     * Builds a segment tree object for Range minimum query
     * Runtime: O(N*logN)
     *
     * @param node     index of the stArray which represents an interval
     * @param interval the interval which is represented by the node
     */
    private void buildSegmentTree(int node, Point interval) {
        if (interval.x == interval.y) {
            stArray[node] = interval.x;
            return;
        }
        Point children = new Point(2 * node + 1, 2 * node + 2);
        buildSegmentTree(children.x, new Point(interval.x, (interval.x + interval.y) / 2));
        buildSegmentTree(children.y, new Point((interval.x + interval.y) / 2 + 1, interval.y));
        stArray[node] = (oArray[stArray[children.x]] <= oArray[stArray[children.y]]) ? stArray[children.x] : stArray[children.y];
    }

    /**
     * Update the value of the array and the corresponding tree
     *
     * @param node      Traversal node index
     * @param cInterval Interval in which the index lies
     * @param index     The index value to be updated
     * @param value     The value with which to be updated
     */
    private void update(int node, Point cInterval, int index, int value) {
        if (cInterval.x == cInterval.y) {
            oArray[index] = value;
            return;
        }

        if (index <= (cInterval.x + cInterval.y) / 2) {
            update(2 * node + 1, new Point(cInterval.x, (cInterval.x + cInterval.y) / 2), index, value);
        } else {
            update(2 * node + 2, new Point((cInterval.x + cInterval.y) / 2 + 1, cInterval.y), index, value);
        }
        stArray[node] = (oArray[stArray[2 * node + 1]] <= oArray[stArray[2 * node + 2]]) ? stArray[2 * node + 1] : stArray[2 * node + 2];
    }

    /**
     * Wrapper method for update
     * Update API
     * Runtime: O(lgN)
     * @param index Index to be updated
     * @param value The value to be updated with
     */
    public void update(int index, int value) {
        update(0, new Point(0, oArray.length - 1), index, value);
    }

    /**
     * @param node Parent of the given sub-segment tree
     * @param cInterval Current interval
     * @param rInterval Required interval
     * @return index of the minimum element in the given range
     */
    private int query(int node, Point cInterval, Point rInterval) {
        if (cInterval.y < rInterval.x || cInterval.x > rInterval.y) {
            return -1;
        }
        if (cInterval.x >= rInterval.x && cInterval.y <= rInterval.y) {
            return stArray[node];
        }

        Point children = new Point(2 * node + 1, 2 * node + 2);
        Point result = new Point();
        result.x = query(children.x, new Point(cInterval.x, (cInterval.x + cInterval.y) / 2), rInterval);
        result.y = query(children.y, new Point((cInterval.x + cInterval.y) / 2 + 1, cInterval.y), rInterval);

        if (result.x == -1) {
            return result.y;
        }
        if (result.y == -1) {
            return result.x;
        }

        return (result.x <= result.y) ? result.x : result.y;
    }

    /**
     * Wrapper method to query from outside
     * Runtime: O(lgN)
     *
     * @param rInterval interval in which minimum is required
     * @return range minimum index
     */
    public int query(Point rInterval) {
        return query(0, new Point(0, oArray.length - 1), rInterval);
    }

    /**
     * Default is to the base e
     *
     * @param x
     * @return log to the base 2
     */
    private double log2(int x) {
        return Math.log(x) / Math.log(2);
    }

    public static void main(String[] args) {
        int[] A = new int[]{8, 7, 3, 9, 5, 1, 10};
        SegmentTree segmentTree = new SegmentTree(A);
        segmentTree.update(6, -1);
        System.out.println(segmentTree.query(new Point(0, 6)));
    }
}

Huffman Coding in Python

Program will take the name of the file (with path is also fine), and will output the compressed file in the directory of the program. This program also shows how to write file byte-wise required for compression.

################################
# Name: Dhruv Pancholi
# Filename: huffman.py
# Input Format: filename
################################

from heapq import *

class Node(object):
	def __init__(self, freq, left = None, right = None, char = None):
		super(Node, self).__init__()
		self.freq = freq
		self.left = left
		self.right = right
		self.char = char
		self.code = [0, 0]
	def __lt__(self, other):
		return self.freq < other.freq
	def __gt__(self, other):
		return self.freq > other.freq
	def __eq__(self, other):
		if other == None:
			return False
		return self.freq == other.freq

def calcFrequency(filename):
	filep = open(filename, 'r')
	freq = {}
	for line in filep:
		for c in line:
			if c not in freq:
				freq[c] = 1
			else:
				freq[c] += 1
	return freq

def huffman(C):
	n = len(C)
	for i in xrange(n-1):
		z = Node(0)
		z.left = heappop(C)
		z.right = heappop(C)
		z.freq = z.left.freq + z.right.freq
		heappush(C, z)
	return heappop(C)

def generateHuffman(root, code, height, code_dict):
	if root==None:
		return
	root.code[0] = code>>1
	root.code[1] = height
	if root.char != None:
		code_dict[root.char] = root.code
	generateHuffman(root.left, code<<1, height+1, code_dict)
	generateHuffman(root.right, (code+1)<<1, height+1, code_dict)

def generateHuffman1(root, code, height, code_dict):
	if root==None:
		return
	root.code = code
	if root.char != None:
		code_dict[root.char] = root.code
	generateHuffman1(root.left, code+'0', height+1, code_dict)
	generateHuffman1(root.right, code+'1', height+1, code_dict)

def calcHuffman(filename):
	code_dict = {}
	freq = calcFrequency(filename)	
	heap = []
	for c in freq:
		heappush(heap, Node(freq[c], char = c))
	root = huffman(heap)
	generateHuffman1(root, '', 0, code_dict)
	return code_dict

def main():
	filename = raw_input('Enter the name of the file to be compressed: ')
	huffman = calcHuffman(filename)
	filep = open(filename, 'r')
	s=''
	for line in filep:
		for c in line:
			s += huffman[c]
	for i in xrange(8-len(s)%8):
		s+='0'
	packed_data = ''.join(chr(int(s[i:i+8], 2)) for i in xrange(0, len(s), 8))
	fileo = open('output.txt', 'w')
	fileo.write(packed_data)
	filep.close()
	fileo.close()
	import os
	print 'Name of the compressed file: output.txt'
	print "Compression ratio: %.6f"%(float(os.stat('output.txt').st_size)/float(os.stat(filename).st_size))

if __name__ == '__main__':
	main()

Hackerrank Algorithmic Crush Solution in Python

from heapq import *

class Node(object):
	def __init__(self, l):
		super(Node, self).__init__()
		# Start, Finish and Weight
		self.s = l[0]; self.f = l[1]; self.w = l[2]
	def __lt__(self, o):
		return self.f < o.f

N, M = map(int, raw_input().split())
A = []; heap = []

for m in xrange(M):
	A.append(Node(map(int, raw_input().split())))

A.sort(key = lambda x: x.s)

maxi = 0; m = 0
for a in A:
	while len(heap)>0 and heap[0].f<a.s:
		m -= heappop(heap).w
	m += a.w
	if m>maxi: maxi = m
	heappush(heap, a)

print maxi

Sample Input:

5 3
1 2 100
2 5 100
3 4 100

Sample Output:

200

Hackerrank Chief Hopper Solution in C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int N; scanf("%d", &N);
    vector <ll> Arr(N);
    for (int i=0;i<N;i++) {
        scanf("%lld", &Arr[i]);
    }
    ll ans = 0;
    for (int i = N-1;i>=0;i--) {
        ans = (Arr[i] + ans)/2 + (Arr[i] + ans)%2;
    }
    printf("%lld\n", ans);
    return 0;
}

Sample Input:

5
3 4 3 2 4

Sample Output:

4

Hackerrank Priyanka and Toys Solution in C++

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>

using namespace std;

int main(){
	int N; scanf("%d", &N);
	priority_queue<int, vector<int>, greater<int> > q;
	int s;
	for(int n = 0; n<N; n++){
		scanf("%d", &s);
		q.push(s);
	}
	int current = 0, count = 0;
	while(!q.empty()){
		current = q.top(); q.pop();
		while(q.top()<=current+4 && !q.empty()) q.pop();
		count++;
	}
	if(count>0) printf("%d\n", count);
	else printf("0\n");
	return 0;
}

Sample Input:

5
1 2 3 17 10

Sample Output:

3

Hackerrank Two Arrays Solution in C++

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>

using namespace std;

int main(){
	int N, K; scanf("%d %d", &N, &K);
	priority_queue<int, vector<int>, greater<int> > q;
	int s;
	for(int n = 0; n<N; n++){
		scanf("%d", &s);
		q.push(s);
	}
	int sum = 0, count = -1;
	while(sum<K && !q.empty()){
		sum += q.top(); q.pop();
		count++;
	}
	if(count>0) printf("%d\n", count);
	else printf("0\n");
	return 0;
}

Sample Input:

2
3 10
2 1 3
7 8 9
4 5
1 2 2 1
3 3 3 4

Sample Output:

YES
NO

Hackerrank Mark and Toys Solution in C++

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>

using namespace std;

int main(){
	int N, K; scanf("%d %d", &N, &K);
	priority_queue<int, vector<int>, greater<int> > q;
	int s;
	for(int n = 0; n<N; n++){
		scanf("%d", &s);
		q.push(s);
	}
	int sum = 0, count = -1;
	while(sum<K && !q.empty()){
		sum += q.top(); q.pop();
		count++;
	}
	if(count>0) printf("%d\n", count);
	else printf("0\n");
	return 0;
}

Sample Input:

7 50
1 12 5 111 200 1000 10

Sample Output:

4

Hackerrank Jim and the Orders Solution in C++

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

int main(){
	int N; scanf("%d", &N);
	vector<pair<int, int> > A;
	int s, f;
	for(int n = 0; n<N; n++){
		scanf("%d %d", &s, &f);
		A.push_back(make_pair(s+f, n));
	}
	sort(A.begin(), A.end());
	for(int n = 0; n<N; n++){
		printf("%d ", A[n].second+1);
	}
	return 0;
}

Sample Input:

3
1 3
2 3
3 3

Sample Output:

1 2 3

Hackerrank Grid Challenge Solution in C++

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int main(){
	int T; scanf("%d", &T);
	while(T--){
		int N; scanf("%d", &N);
		char A[N][N];
		for(int n = 0; n<N; n++){
			scanf("%s", A[n]);
			sort(A[n], A[n]+N);
		}
		bool b = false;
		for(int i = 0; i<N; i++){
			if(b) break;
			for(int j = 0; j<N-1; j++){
				if(A[j+1][i]<A[j][i]){
					b = true;
					break;
				}
			}
		}
		if(!b) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Sample Input:

1
5
ebacd
fghij
olmkn
trpqs
xywuv

Sample Output:

YES