Find next greatest number from digits of a given number

Find the smallest number that has same set of digits as n and is greater than n. 
If n is the greatest possible number with its set of digits, then print "not possible".

Examples:

Input:  n = "1234"
Output: "1243"

Input:  n = "1243"
Output: "1324"

Input:  n = "1324"
Output: "1342"

Input:  n = "1342"
Output: "1423"

Input: n = "4321"

Output: "Not Possible"

Input:  n = "5349762"
Output: "5362479"

Input: n = "53497766"
Output: "53646779"

Algorithm:

From the first few examples, we can see that the algorithm is to traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. Then replace this small number with the next highest traversed number. Then pick remaining traversed number plus the small number, sort them from smallest to largest and append them to the end. 

package com.prasune.coding; import java.util.Set; import java.util.TreeSet; public class NextGreatestNumber {       public static void main(String[] args) {             printNextGreaterNumber(4321);       }       private static void printNextGreaterNumber(Integer number) {             String nextGreaterNumber = null;             String numberAsString = number.toString();             Integer prevValue = 0;             Set<Integer> numbersToSort =                   new TreeSet<Integer>(new CustomComparator());                                 for (int i = numberAsString.length() - 1; 0 <= i; i--) {                   Integer digit =                   Integer.parseInt(""+numberAsString.charAt(i));                                if(digit < prevValue){                         Integer replacement =                                     getReplacementNumber(digit, numbersToSort);                         nextGreaterNumber = numberAsString.substring(0, i)                                           + replacement;                         numbersToSort.add(digit);                         nextGreaterNumber = appendSortedNumbers(                                               nextGreaterNumber,                                                              numbersToSort,                                                                  replacement);                         break;                   } else{                         prevValue = digit;                   }                       numbersToSort.add(digit);             }             if(nextGreaterNumber != null){                   System.out.println("Next greater number: "                                       + nextGreaterNumber);             }else{                   System.out.println("Not Possible");             }                 }       private static Integer getReplacementNumber(Integer digit,                                                                  Set<Integer> numbersToSort) {             Integer replacementNumber = 0;             for (Integer number : numbersToSort) {                   if(number > digit){                         replacementNumber = number;                         break;                   }             }             return replacementNumber;       }       private static String appendSortedNumbers(String nextGreaterNumber,                                                 Set<Integer> numbersToSort,                                                 Integer replacement) {             boolean isReplacementExcluded = false;             StringBuilder greaterNumberString =                                       new StringBuilder(nextGreaterNumber);             for (Integer number : numbersToSort) {                   if(!isReplacementExcluded && number == replacement){                         isReplacementExcluded = true;                                     }else {                         greaterNumberString.append(number);                   }             }             return greaterNumberString.toString();       }     }

Program to find shortest distance to particular value in a matrix

Given a matrix of -1's and 0's, display a matrix which contains minimum distance to reach nearest 0 from that particular position.
Example:
Input1: 
-1,0,-1
-1,-1,-1
-1,-1,-1
Output: 
1,0,1
2,1,2
3,2,3

Input2: 
-1,0,-1
-1,-1,-1
-1,0,-1
Output:
1,0,1
2,1,2
1,0,1

Algorithm:
1. Figure out the all positions in matrix having zero and cache them.
2. Calculate the distance from each position to the cached zero positions by summing absolute distance of x and y co-ordinates.
3. Put the minimum value in the result matrix.

package com.prasune.coding; import java.util.ArrayList; import java.util.List; public class ShortestDistance {       public static void main(String[] args) {             int matrix[][] = {                                   {-1,0,-1},                                   {-1,-1,-1},                                   {-1,0,-1}                                  };             printAsMatrix(matrix);             printDistanceToZero(matrix);       }       private static void printDistanceToZero(int[][] matrix) {             int[][] resultMatrix = new int[matrix.length][matrix.length];             List<Position> zeroPositions = new ArrayList<Position>();                         for (int i = 0; i < matrix.length; i++) {                   for (int j = 0; j < matrix[i].length; j++) {                         if(matrix[i][j] == 0){                               zeroPositions.add(new Position(i,j));                         }                                         }             }                         for (int i = 0; i < matrix.length; i++) {                   for (int j = 0; j < matrix[i].length; j++) {                         if(matrix[i][j] == 0){                               resultMatrix[i][j] = 0;                         } else{                               int minValue = Integer.MAX_VALUE;                               for (Position position : zeroPositions) {                                     int tempMinValue = Math.abs(i - position.getRowNum()) +                                                                Math.abs(j - position.getColNum());                                     if(tempMinValue < minValue){                                           minValue = tempMinValue;                                     }                               }                               resultMatrix[i][j] = minValue;                         }                                                           }             }             printAsMatrix(resultMatrix);       }       private static void printAsMatrix(int[][] matrix) {             for (int i = 0; i < matrix.length; i++) {                   for (int j = 0; j < matrix[i].length; j++) {                         System.out.print(matrix[i][j]);                         if(j < matrix[i].length-1){                               System.out.print(",");                         }                                         }                   System.out.println();             }       } }

Position.java

package com.prasune.coding; public class Position {       private int rowNum;       private int colNum;             public Position(int rowNum, int colNum) {             this.rowNum = rowNum;             this.colNum = colNum;       }       public int getRowNum() {             return rowNum;       }       public void setRowNum(int rowNum) {             this.rowNum = rowNum;       }       public int getColNum() {             return colNum;       }       public void setColNum(int colNum) {             this.colNum = colNum;       } }

Add two large numbers that cannot be stored in numeric data types

You are given two numbers as String which are so large that it cannot be stored in any of the numeric data types. You need to return the sum of these numbers as String.

"it cannot be stored in any of the numeric data types" means it includes Long, BigDecimal etc.. Assume around 1000 digits in the number

package com.prasune.coding; import java.util.Stack; public class AddBigNumbers {       public static void main(String[] args) {             String number1 = "123456789129";             String number2 = "345343";             System.out.println(add(number1, number2));       }       public static String add(String number1, String number2){             String result = "";             Stack<Integer> n1 = new Stack<Integer>();             Stack<Integer> n2 = new Stack<Integer>();             Stack<Integer> sum = new Stack<Integer>();             int carryForwardValue = 0;             for (int i = 0; i < number1.length(); i++) {                   n1.push(Integer.parseInt("" + number1.charAt(i)));             }             for (int i = 0; i < number2.length(); i++) {                   n2.push(Integer.parseInt("" + number2.charAt(i)));             }             while(!n1.empty() || !n2.empty()){                   int digit1 = 0;                   int digit2 = 0;                   if(!n1.empty()){                         digit1 = n1.pop();                   }                   if(!n2.empty()){                         digit2 = n2.pop();                   }                                   int sumOfNumbers = digit1 + digit2 + carryForwardValue;                   sum.push(sumOfNumbers % 10);                   carryForwardValue = sumOfNumbers/10;             }             while(!sum.empty()){                   result = result + sum.pop();             }             return result;       } }

Program to reverse a given sentence in java

Write a program to reverse a sentence in Java

For example if you have a sentence "Quick brown fox jumped over a lazy dog",

your output should be "dog lazy a over jumped fox brown Quick"

package com.prasune.coding; import java.util.Stack; import java.util.StringTokenizer; public class ReverseSentence {       public static void main(String[] args) {             System.out.println(getReverseString("Quick brown fox jumped over a lazy dog"));       }       public static String getReverseString(String str){         StringTokenizer tokenizer = new StringTokenizer(str);         Stack<String> stack = new Stack<String>();         String reversedString = "";         while(tokenizer.hasMoreTokens()){           stack.push(tokenizer.nextToken());         }         while(!stack.empty()){               reversedString = reversedString + stack.pop() + " ";         }         return reversedString.trim();       } }