Arbitrary Precision Types In Java

QUESTION : 
What will be the output in the following code snippet?

Here's the snapshot of the output of the above function

NOTE : 
For built-in primitive data types such as int, long, double, etc. Java never throws any overflow or underflow exception, even though the size and the bounds for these data types is defined. 

Why? Because all data is internally stored by the JVM in binary-format. Thus, in actual memory, each variable, whether int or double is stored as a string of 1's and 0's. There is no concept of a "negative sign" in binary system. Negative numbers are stored in a special format called 2's complement . 

Hence, when the bound on any data type is reached and exceeded, the JVM simply reverses the sign of the number and prints the largest number in that sign. For example, in the above example, if we exceed 2147483647 which is the upper bound on int, the sign is reversed to negative and the value of smallest possible int is printed.

How do we avoid this? By casting the number into a larger data type and checking its value. If indeed, overflow or underflow has occurred, we can throw an exception and take the necessary rectification. Following is a code snippet which illustrates this.

What if overflow/underflow is a valid case in my problem?
Overflow is a valid case practically when problems involving very large numbers are present. In such cases, a way to implement variables is to use Arbitrary Precision Data Types. Java offers 2 arbitrary precision types : BigInteger and BigDecimal in java.math library.

The word "arbitrary precision" means that a variable of such type uses exactly as much space as required or mentioned. Thus, the precision is "set" according to our needs. Theoretically, there is no limitation to the size, the only limitations being that of insufficient memory. 

It is important to note that these data types are implemented internally as a collection of primitive data type. Thus, BigInteger is implemented as an array of ints. Also, these are implemented classes and not default and Java does not allow operator overloading. Thus, primitive operations such as addition, multiplication, power, etc. although present for these classes, do not use operators such as "+", "*" etc. Instead, they use functions such as a.add(b), a.multiply(b), etc. Since the use of functions is involved, the operations tend to be slower.

BigInteger is generally used for large integers and BigDecimal is used when extremely high levels of precisions is required (1000th decimal place of π).

Tic Tac Toe Applet

Here is a simple two-player Tic Tac Toe applet, just to get familiar with ActionListeners and basic GridView. Hopefully, the code below is well-commented and self-explanatory.


Here are some snaps of the output :

Smallest Sum Not Present In An Array

INPUT :
An array "A" of size "n".

OUTPUT :
The smallest integer that cannot be represented by the sum of any subset of "A".
E.g. if A = {1, 1, 1, 1}, output = 5; if A = {1, 2, 3, 4, 5}, output = 16

BRUTE FORCE METHOD :
The simplest and possibly the worst method would be to find out all the subsets of A and store each's sum in a Hash Map, then keep an integer i starting from 1 and check every time whether any sum equals to i. This method, is not only inefficient in nature, but also can be unsolvable in the sense that it can be, in worst cases, a NP-Complete problem .

PRE-REQUISUTE :
Before we actually look into our algorithm, let us do a little background. If someone asks you to give a list of numbers that can, with the sum of any of its sub-sets, give a result upto 2^k-1, what numbers do you choose? It is proven mathematically that you need a minimum of k numbers. And each of these numbers is a power of 2. 

So, if given k numbers, all subsequent powers of starting from 1; we can form all numbers from 1 to 2^k, from them. For example, an array {1, 2, 4, 8, 16} can be used to form all numbers from 1-31. This property forms the basis of Binary Number System. Thus, a 5 bit binary number can represent upto 2⁵-1 = 31 i.e. in total, 32 numbers.

OUR APPROACH :
We first sort the array in ascending order. Using the property mentioned above, we assume the entire array to be consisting of powers of 2 or, since its the decimal system, consisting of only consecutive numbers. If our assumption is true and the array indeed consists of only powers of 2 or consecutive integers, then the least number will be 2ⁿ-1, where n is the length of the array. If our assumption fails at any point, then we have found the "gap" in the sequence and the sum of all elements uptill that point is our answer.

We first sort the array in ascending order. We keep a pointer "i" such that "i" traverses the given array A. We also keep a variable "sno" which is the smallest sum initialized at 1. Then we check whether "sno" is lesser than A[ i ], if it is, then we print "sno". Otherwise, we increment "sno" by A[ i ].
 
Algorithm SmallestSum(A)

1. QuickSort(A);
2. sno = 1, i = 1;
3. Traverse A
4.          if(sno >= A[ i ])
5.                 sno += A[ i ];
6.           else return sno;
   

The Java implementation of QuickSort can be found here . The Java implementation of the algorithm is as follows: Note that, ignoring the time efficiency of QuickSort, the algorithm executes in O(n) time. Also note that, since we have extended the logic behind Binary Number System and negative numbers cannot be represented by this system (they are usually represented in sign-magnitude form, wherein the magnitude is always positive. Even the 2's complement form is just a positive number taken with different meaning, e.g. 1110 is either +15 or -2 in 2's complement form), our algorithm will not work for negative numbers. If you find any algorithm which does work for negative integers too, feel free to provide a link in the comments.

Intersection And Union Of Arrays

INPUT : Two Arrays "A" and "B" consisting of "n" and "m" elements respectively.

OUTPUT :
The union "U" of the two arrays and the intersection "I" of the arrays.
Example : if A = {1, 2, 4, 8}, B = {2, 6, 8, 10} then,
                U = {1, 2, 4, 6, 8, 10}, I = {2, 8}
Note : Since arrays are fundamentally different from Sets in the sense that every element is unique, we neglect the repeating elements in the union and the intersection as well i.e. if A = {1, 1, 1} and B = {1, 1} then, U = {1, 1, 1, 1, 1} and I = {1, 1}. This is because each element in an array is fundamentally unique.

OUR APPROACH :
 The first step is to sort each array in the same order (we used quick-sort to sort the array in ascending order). For each of the 2 functions (union and intersection), we maintain 2 pointers, one for each array. Now, we compare the elements at the ith position of A and jth position of B. Since the arrays are in increasing order, we know that if A[ i ] < B[ j ], the value equal to B[j] will be found only on the right side of i and vice versa. Thus, we traverse the 2 arrays and store the required elements.

The Java code for the said functions is as follows:
The Java implementation of QuickSort can be found here .
Note that, if we ignore the running time of QuickSort, the running time of each of the two functions is O(n+m).

Run Length Encoding

INPUT :
A string "s" consisting of possibly repeating characters. 
E.g. "aaaaabbbcddddefgttt"

OUTPUT :
A string s' such that s'.length() <= s.length(). String shortening is done by counting the contiguous occurrence of the characters and replacing them by the single character and its count of occurrence.
E.g. "a5b3cd4efgt3" 

Wikipedia Page