Partition to two subsets

 Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.

Examples

arr[] = {1, 5, 11, 5}
Output: true
The array can be partitioned as {1, 5, 5} and {11}

arr[] = {1, 5, 3}

Output: false

The array cannot be partitioned into equal sum sets.

 

Following are the two main steps to solve this problem:

1) Calculate sum of the array. If sum is odd, there cannot be two subsets with equal sum, so return false.

2) If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.

The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.

public static boolean subSetSum(int[] a, int n, int sum) {

if(sum == 0) {

return true;

}

if(n == 0 && sum != 0) {

return false;

}

if(a[n]>sum) {

subSetSum(a, n-1, sum);

}

return subSetSum(a, n-1, sum-a[n]) || subSetSum(a, n-1, sum);

}

public static boolean partitionTwoSubsets(int[] a) {

int totalSum = 0;

for(int i=0; i<a.length; i++) {

totalSum += a[i];

}

if(totalSum % 2 != 0) {

return false;

}

else {

return subSetSum(a, a.length-1, totalSum/2);

}

}

Longest Palindromic Substring

Given a string, find the longest substring which is palindrome. For example, if the given string is “forgeeksskeegfor”, the output should be “geeksskeeg”.

    public static String getPalindromicSubstring(String s, int l, int r) {

while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)) {

l--;

r++;

}

return s.substring(l+1, r);

}

public static String longestPalindromicSubstring(String str) {

String longestPalin = "";

for(int i=0; i<str.length()-1; i++) {

String palin = getPalindromicSubstring(str, i, i);

if(palin.length() > longestPalin.length()) {

longestPalin = palin;

}

palin = getPalindromicSubstring(str, i, i+1);

if(palin.length() > longestPalin.length()) {

longestPalin = palin;

}

}

return longestPalin;

}

Subset Sum Problem

 Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems

…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]

…b) Exclude the last element, recur for n = n-1.

If any of the above subproblems return true, then return true.

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) ||
                           isSubsetSum(arr, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0

Sol:

public static boolean subSetSum(int[] a, int n, int sum) {
    if(sum == 0) {
	return true;
    }		
    if(n == 0 && sum != 0) {
        return false;
    }		
    if(a[n]>sum) {
	subSetSum(a, n-1, sum);
    }		
    return subSetSum(a, n-1, sum-a[n]) || subSetSum(a, n-1, sum);
}

Replace every element with the next greatest

 Replace every element with the next greatest.

Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element, replace it with -1. For example, if the array is {16, 17, 4, 3, 5, 2}, then it should be modified to {17, 5, 5, 5, 2, -1}.

public static int[] replaceGreatestNumber(int[] a) {

int n = a.length;

int max = a[n-1];

a[n-1] = -1;

for(int i=n-2; i>=0; i--) {

int temp = a[i];

a[i] = max;

if(temp > max) {

max = temp;

}

}

return a;

}

Largest K numbers in a million numbers which are in random order

 Let's find out largest k numbers in a million numbers which are in random order

Sol:

public static void largestKNumbers(Integer[] a, int k) {

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);

for(int i=0; i<k; i++) {

minHeap.add(a[i]);

}

for(int i=k; i < a.length; i++) {

if (a[i] > minHeap.peek()) {

minHeap.poll();

minHeap.add(a[i]);

}

}

Iterator iterator = minHeap.iterator();

while(iterator.hasNext()) {

System.out.print(iterator.next() + " ");

}

}