Maximum Sum Path in Two Arrays

Given two sorted arrays such the arrays may have some common elements. Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can switch from one array to another array only at common elements.

Note : Imp to execute and trace to understand and remember

package testPackage;

public class maxPathSum{
		public static void main(String args[]){
			int a[]={2,3,7,8,10,11};
			int b[] = {1,5,6,7,10,12};
			int n = a.length;
			int m = b.length;
			int i=0,j=0,sum1=0,sum2=0,sum=0,max=0,startpoint1=0,startpoint2=0;
			
			while(ib[j])
				{
					sum2=sum2+b[j];
					j++;
				}
				else if(a[i]<b[j]) 				{ 					sum1 = sum1 + a[i]; 					i++; 				} 				else if(a[i]==b[j]) 				{ 					if(sum1>sum2)
					{
						max=sum1;
						for(int p=startpoint1 ; p <=i ; p++)
							System.out.print(" " + a[p]);
					
					}
					else
					{
						max = sum2;
						for(int p=startpoint2 ; p <=j ; p++)
							System.out.print(" " + b[p]);
					}
					startpoint2=j+1;
					startpoint1=i+1;
				
					sum = sum + max + a[i];
			
					i++;
					j++;
					sum1=0;
					sum2=0;
							
				}
				else
				{
					System.out.println("Error!");
				}
			}
		
			while(i<n)
			{
				sum1 = sum1 + a[i];
				i++;
			}
			while(j<m) 			{ 				sum2 = sum2 + b[j]; 				j++; 			} 			if(sum1>sum2)
			{
				max=sum1;
				for(int p=startpoint1 ; p 

Check for balanced parentheses in an expression

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”

Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”

public static void main(String[] args) {
		String str = "[()]{}{[()()]()}";
		if(checkBalancedParanthesis(str))
			System.out.println("Balanced Paranthesis");
		else
			System.out.println("Not Balanced Paranthesis");
	}
	
	public static Boolean checkBalancedParanthesis(String str)
	{
		HashMap<Character, Character> hm = new HashMap<Character, Character>();
		hm.put('[', ']');
		hm.put('(', ')');
		hm.put('{', '}');
		
		Stack st = new Stack();
		
		//Odd no. of characters => not balanced
		if(str.length() % 2 != 0)
			return false;
		
		for(int i =0;i<str.length();i++)
		{
			//opening brace
			if(hm.containsKey(str.charAt(i)))
			{
				st.push(str.charAt(i));
			}
			//closing brace
			else
			{
				if(st.isEmpty())
					return false;
				
				if(hm.get(st.pop()) != str.charAt(i))
					return false;
			}
		}		
		if(st.isEmpty())
			return true;
		else
			return false;
	}

Ugly Numbers Program

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150’th ugly number.

# include
# include
 
/*This function divides a by greatest divisible 
  power of b*/
int maxDivide(int a, int b)
{
  while (a%b == 0)
   a = a/b; 
  return a;
}   
 
/* Function to check if a number is ugly or not */
int isUgly(int no)
{
  no = maxDivide(no, 2);
  no = maxDivide(no, 3);
  no = maxDivide(no, 5);
   
  return (no == 1)? 1 : 0;
}    
 
/* Function to get the nth ugly number*/
int getNthUglyNo(int n)
{
  int i = 1; 
  int count = 1;   /* ugly number count */
 
  /*Check for all integers untill ugly count 
    becomes n*/
  while (n > count)
  {
    i++;      
    if (isUgly(i))
      count++; 
  }
  return i;
}
 
/* Driver program to test above functions */
int main()
{
    unsigned no = getNthUglyNo(150);
    printf("150th ugly no. is %d ",  no);
    getchar();
    return 0;
}

This method is not time efficient as it checks for all integers until ugly number count becomes n, but space complexity of this method is O(1)

Methods to use involve dynamic programming, google it

Program to print all permutations of a given string(Backers Algorithm)

Below are the permutations of string ABC.
ABC, ACB, BAC, BCA, CAB, CBA

Here is a solution using backtracking.

public class TestClass {

	public static void main(String[] args) {
		char a[] = new char[3];
		a[0] = 'A';
		a[1] = 'B';
		a[2] = 'C';
		permute(a, 0, a.length-1);
	}
	
	/* Function to print permutations of string
	   This function takes three parameters:
	   1. String
	   2. Starting index of the string
	   3. Ending index of the string. */
	public static void permute(char[] a, int i, int n) 
	{
	   int j; 
	   if (i == n)
	     System.out.println(a);
	   else
	   {
	        for (j = i; j <= n; j++)
	       {
	          a = swap(a,i,j);
	          permute(a, i+1, n);
	          a = swap(a,i,j); //backtrack
	       }
	   }
	} 
	public static char[] swap (char[] a,int index0,int index1  )
	{
	    char temp;
	    temp = a[index0];
	    a[index0] = a[index1];
	    a[index1] = temp;
	    return a;
	}

}