Constructing a balanced Binary Search Tree from a sorted List in O(N) time

This post discusses a O(n) algorithm that construct a balanced binary search tree (BST) from a sorted list. For instance, consider that we are given a sorted list: [1,2,3,4,5,6,7]. We have to construct a balanced BST as follows.

        4
        |
    2        6 
    |        |
  1   3   5     7

To do so, we use the following definition of Tree, described in Scala By Example book.

abstract class IntSet
case object Empty extends IntSet
case class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet

One straight-forward approach would be to repeatedly perform binary search on the given list to find the median of the list, and then, to construct a balanced BST recursively. Complexity of such approach is O(nlogn), where n is the number of elements in the given list.

A better algorithm constructs balanced BST while iterating the list only once. It begins with the leaf nodes and construct the tree in a bottom-up manner. As such, it avoids repeated binary searches and achieves better runtime complexity (i.e., O(n), where n is the total number of elements in the given list). Following Scala code outlines this algorithm, which effectively converts a list ls to an IntSet, a balanced BST:

def toTree(ls: List[Int]): IntSet = {
def toTreeAux(ls: List[Int], n: Int): (List[Int], IntSet) = {
if (n <= 0)
(ls, Empty)
else {
val (lls, lt) = toTreeAux(ls, n / 2) // construct left sub-tree
val x :: xs = lls // extract root node
val (xr, rt) = toTreeAux(xs, n - n / 2 - 1) // construct right sub-tree
(xr, IntSet(x, lt, rt)) // construct tree
}
}
val (ls_1, tree) = toTreeAux(ls, List.length(ls))
tree
}
view raw toTree.scala hosted with ❤ by GitHub

Any comment or query regarding this post is highly appreciated. Thanks.

UVa 136. Ugly Numbers

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:

1,2,3,4,5,6,8,9,10,12,15...

Using F#, we can derive 1500th Ugly Number in F#’s REPL as follows.

seq{1L..System.Int64.MaxValue}
|> Seq.filter (isUglyNumber)
|> Seq.take 1500
|> Seq.last
view raw gistfile1.fs hosted with ❤ by GitHub

In this context, the primary function the determines whether a number is a Ugly number or not–isUglyNumber–is outlined as follows. As we can see, it is a naive algorithm that can be further optimized using memoization (as listed here).

(*
* :a:int64 -> b:bool
*)
let isUglyNumber (x:int64) :bool =
let rec checkFactors (n_org:int64) (n:int64) lfactors =
match n with
| 1L -> true
| _ ->
match lfactors with
| [] -> false
| d::xs ->
if isFactor n d then
checkFactors n_org (n/d) lfactors
elif n > d then
checkFactors n_org n xs
else
false
checkFactors x x [2L;3L;5L]
view raw gistfile1.fs hosted with ❤ by GitHub

After computing the 1500th Ugly number in this manner, we submit the Java source code listed below. For complete source code. please visit this gist. Alternatively, this script is also available at tryfsharp.org for further introspection.

class Main {
public static void main(String[] args) {
System.out.println("The 1500'th ugly number is 859963392.");
}
}
view raw gistfile1.java hosted with ❤ by GitHub

Please leave a comment in case of any question or improvement of this implementation. Thanks.

UVa 371. Ackermann Function

The underlying concepts of UVa 371: Ackermann Functions have been discussed in great details in our post of Collatz problem. In this post, we simply outlines an ad-hoc algorithm as a solution to this problem as follows.

import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
private final Scanner in;
private final PrintWriter out;
private final static int _MaxValue = 1000000;
private final static long[] memo = new long[_MaxValue];
public Main() {
in = new Scanner(System.in);
out = new PrintWriter(System.out, true);
}
public Main(Scanner in, PrintWriter out) {
this.in = in;
this.out = out;
}
private static long[] getInts(String input) {
String[] ints = input.trim().split(" ");
long[] rets = new long[2];
rets[0] = Long.parseLong(ints[0]);
rets[1] = Long.parseLong(ints[1]);
return rets;
}
private void solveAckermannProblem(long from, long to) {
long maxValue = from;
long maxLength = 0;
for (long i = from; i <= to; i++) {
long length = computeCycleLength(nextAckermannNumber(i));
if (maxLength < length) {
maxValue = i;
maxLength = length;
}
}
out.println(String
.format("Between %d and %d, %d generates the longest sequence of %d values.",
from, to, maxValue, maxLength));
}
private static long computeCycleLength(long n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
if (n < _MaxValue && memo[(int) n] != 0)
return memo[(int) n];
long len = 1 + computeCycleLength(nextAckermannNumber(n));// computing
// length of
// Ackermann
// sequence
if (n < _MaxValue) // storing it in cache
memo[(int) n] = len;
return len;
}
public static long nextAckermannNumber(long n) {
if (n % 2 == 0)
return n / 2;
else
return n * 3 + 1;
}
public void run() {
while (in.hasNextLine()) {
long[] range = getInts(in.nextLine());
if ((range[0] == 0) && (range[1] == 0))
break;
long from = Math.min(range[0], range[1]);
long to = Math.max(range[0], range[1]);
solveAckermannProblem(from, to);
}
}
public static void main(String[] args) {
Main solver = new Main();
solver.run();
}
}
view raw UVa371.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.


See Also

see Collatz Problem a.k.a. 3n+1 ProblemCollatz Problem a.k.a. 3n+1 Problem.
see UVa100. 3n+1 ProblemUVa 100. 3n+1 Problem.

UVa 713. Adding Reversed Numbers

UVa 713: Adding Reversed Numbers is a straight-forward problem that can be solved using an ad-hoc algorithm. We have discussed a similar problem in a previous blog-post. However, this problem imposes following additional constraint—numbers will be at most 200 characters long–which necessitates the use of BigInteger. Following Java code shows such an ad-hoc algorithm that solves this problem by considering the stated constraints.

import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;
class Main {
private final Scanner in;
private final PrintWriter out;
public Main(){
in = new Scanner(System.in);
out = new PrintWriter(System.out, true);
}
public Main(Scanner in, PrintWriter out){
this.in = in;
this.out = out;
}
private static BigInteger bigIntAfterRemovingTrailingZeros(String num){
int nonZeroIndex=num.length()-1;
for (; nonZeroIndex>=0; nonZeroIndex--){
if (num.charAt(nonZeroIndex) != '0'){
break;
}
}
return new BigInteger(num.substring(0, nonZeroIndex+1));
}
private static BigInteger[] readLineAsBigInts(String input){
String [] ints = input.trim().split(" ");
BigInteger [] rets = new BigInteger[2];
rets[0] = bigIntAfterRemovingTrailingZeros(ints[0]);
rets[1] = bigIntAfterRemovingTrailingZeros(ints[1]);
return rets;
}
private static BigInteger reversedBigInt(BigInteger num1){
BigInteger reversedNum = BigInteger.ZERO;
final int _REM = 1;
final int _QUOTIENT = 0;
while (num1.compareTo(BigInteger.ZERO)>0){
BigInteger [] results = num1.divideAndRemainder(BigInteger.TEN);
reversedNum = reversedNum.add(results[_REM]);
if(num1.compareTo(BigInteger.TEN)>=0)
reversedNum =reversedNum.multiply(BigInteger.TEN);
num1 = results[_QUOTIENT];
}
return reversedNum;
}
private static BigInteger getAddRevNumbers(BigInteger num1, BigInteger num2){
return reversedBigInt(reversedBigInt(num1).add(reversedBigInt(num2)));
}
public void run(){
final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases
BigInteger [] numbers;
for (int testCase = 0 ; testCase< T ; testCase++){
numbers = readLineAsBigInts(in.nextLine());// read input
out.println(getAddRevNumbers(numbers[0], numbers[1]));// print result
}
}
public static void main(String[] args) {
Main uva713Solver = new Main();
uva713Solver.run();
}
}
view raw uva713.java hosted with ❤ by GitHub

Please leave a comment if you have any question. Thanks.


See Also

see Party Schedule postSPOJ 42. Adding Reversed Numbers (ADDREV) with F#.