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

Number Of Possible Triangles In An Array

We have "n" sticks with us. The length of each stick is known to us. We need to find the number the triangles that can possibly be made from these sticks. The condition for making a triangle is that the sum of any two sides of the triangle should be greater than the third side. i.e. if a, b, c form a triangle, then :
1) a+b>c
2) b+c>a
3) a+c>b

INPUT:
The first input will be "n" i.e. the number of sticks in our hands. The second input will be an array of the lengths of each stick i.e. the size of the array will be "n".

OUTPUT:
The number of triangles possible. For example, for an input array {14, 8, 2, 1, 3, 9}, the 3 possible triangles are : (14, 8, 9) , (8, 3, 9), (8, 2, 9). So the output should be 3.

BRUTE FORCE METHOD:
The brute-force method dictates that we take every combination of 3 elements in the array and check if the triangle-conditions 1), 2), 3) hold. Thus, for n sticks, we will have ⁿC₃ = ϴ(n³) comparisons. Following is the brute force approach:

Algorithm bruteForce(int[n] a)

1. For (i = 0 upto n-3)
2.      For(j = i+1 upto n-2)
3.           For(k = j+1 upto n-1)
4.                  if(a[i]+a[j] > a[k] AND a[j]+a[k] > a[i] AND a[i]+a[k] > a[j])
5.                        count++

A BETTER APPROACH:
Instead of the brute-force approach, we make use of a simple mathematical manipulation:
If in a combination (a, b, c), a is the greatest element, and if b+c > a, then  (a, b, c) can form a triangle.

This manipulation is illustrated as follows : 
Consider a combination (14, 8, 9). Here 14 is the greatest element in the combination. Now, 8+9 = 17 > 14. Thus, condition 2) is satisfied. Now, since we know that 14 is the largest element, we will be sure that 14 + 8 or 14 + 9 will surely exceed the other element. Thus conditions 1) and 3) are satisfied and a triangle is possible.

The above approach first sorts the array in a descending order so that the initial elements will be the largest. We then traverse through the array and check for any combination of 3 elements whose sum of 2 exceeds the first. If we do not find such pairs, we stall the traversal.

Note that the above approach is what can be called as "output-dependent". If, in an array of size "n", there are "m" triangles possible, then the maximum number of comparisons will be n+m-3 which is much much lesser that n³. Thus, we have eliminated a lot of redundant comparisons and made our program quicker. As a result, athough the program implements 3 nested for-loops, by eliminating redundancy, we have greatly improved the efficiancy of the program.

Number Of Occurences Of A Word In A Sentence

INPUT: A sentence containing one or many words like "Hello World Hello Java". We assume that no punctuation marks have been used.

OUTPUT: The number of occurenes of each word. For example, in the above example, the output we get is:
Hello - 2
World - 1
Java - 1
Note that the words "Hello" and "hello" are not the same i.e. the words are case-sensitive

BRUTE FORCE METHOD:
The first step is to break the sentence into words. We then store the words in an ArrayList for ease.

The brute force method is obviously to compare every word in the sentence with every other word. This will take ϴ(n²) for a n-worded sentence as it will involve 2 nested for-loops and every possible pair will be checked.

HASH-MAP IMPLEMENTATION:
In this approach, the first step remains the same - to break the sentence up ino words and arrange the in an ArrayList. Note that this step costs ϴ(n) as 1 full traversal of the array is needed.

However, we now count the number of occurences using Hash-Map instead. We create a HashMap named "map" which has the ASCII value of each word as its key and the word itself as its value. We then iterate over this HashMap and print count of each word. To store count, we either implement another HashMap or a set of variables.

Note that the above step finds the number of occurences in O(n) time. The worst case will be achieved when each word is distinct in the sentence. Thus, at the cost of O(n) extra memory, we reduced the ime-complexity of the programme from ϴ(n²) to O(n).

Implementation Of Quick Sort

We have observed that although the logic behind quick sort is quite simple and straight-forward, people do find it a bit difficult to implement. So we have implemented this very useful and efficient (O(n*log₂n)) sort in java. It has been tested for all cases, yet if you find any flaws in it, please leave a comment.

The logic behind this quick sort implementation is picked up from CLRS 3rd edition. 
 

Longest Palindrome In The String

INPUT :
A string of length n.

OUTPUT :
A palindromic string which is the longest sub-string of the inputted string. Thus the output string can have a maximum length of 'n'

THE BRUTE FORCE METHOD :
Since we are looking for a sub-string, the brute force method would suggest finding every possible sub-string in the string and checking if its a palindrome. The algorithm to find every sub-string accepts the inputted string 's' and its length 'n' as parameters. We assume the existence of a pseudo function isPalindrome which accepts a string as parameter and returns true if the string is a palindrome and false otherwise. We also assume subString(String, startIndex, endIndex) to be a function that returns the substring of s beginning from startIndex (including) and ending at endIndex (excluding). This is quite similar to the Java.lang.String.substring(int beginIndex, int endIndex). The algorithm uses 3 variables : maxlen to find out the maximum length of the palindrome, templen to compare with maxlen, start and end as the begin and end indices of the palindrome respectively.

Algorithm findSubString (String s)

1. maxlen = 0 ,  templen = 0, start = 0, end = 0
2. for (int i = 0 up to n-1) 
3.      for (int j = i down to 0)
4.            for (int k = i+1 up to n)
5.                          templen = k-j+1
6.                          if ( isPalindrome(subString(s, j, k+1)) && templen > maxlen) 
7.                               maxlen = templen
8.                               start = j
9.                               end = k+1 // k+1 is because subString excludes the endIndex
10.                          end if
11.               end for
12.         end for
13. end for
14. return subString(s, start, end)

However, as we see, this approach uses 3 traversals in 3 nested for loops, taking O(n³) time. It should be noted that the time-efficiency of the function isPalindrome() is not taken into consideration as it is, anyways, less than O(n³) (shall be proved in a few moments).

THE isPalindrome() FUNCTION :
The most efficient method of determining whether a string is palindrome or no is to start with its central character and to go one character each to the left and right simultaneously checking whether the string is a palindrome. For example, for "abcba", we start at "c", which is the central character and then go one character to the left getting "b" and one character to the right getting "b" again. Thus "bcb" is a palindrome. We go on doing this till the string stops being a palindrome. This is essentially the algorithm behind isPalindrome(). Let us say that we divide every palindromic string of length, say p, into 2 kinds : when p is even and when p is odd. 

1.  when p is odd, as in "abcba", we fix 1 mid-point (here "c"), then compare every character at an "x" distance from it to the left to every character at the same distance from it to the right.
2. when p is even, like "abccba", we fix no mid-point, and begin comparing from "c" and "c" (they occupy the center positions in the string; 6/2 = 3 therefore 3rd and 4th positions are central) and then continue as above.

Thus we see, that any string can be checked for palindrome in O(n) times (1 traversal).

A BETTER APPROACH :
Note that we need to find a palindromic sub-string. Such a sub-string may begin or end at any index in the string, and not necessarily at the beginning and the end of the string. For example, for "banana", the longest palindromic sub-string is "anana" which doesn't start at the beginning of the string. So to speak, we do not know the start or the end of the sub-string and thus we cannot find the mid-point. Hence, we need to consider every character as the mid-point and begin checking for the palindromes. This will take 1 traversal of the string. A java code implementing this approach is as follows :

Do leave any comments if you find a better approach or if you have any doubts regarding the given approach. 

Courtesy : http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/