fork(12) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. class NextBiggerPalindromeNumber {
  5.  
  6. 	/**
  7. Given a number, find the next smallest palindrome
  8. Given a number, find the next smallest palindrome larger than this number. For example, if the input number is “2 3 5 4 5″, the output should be “2 3 6 3 2″. And if the input number is “9 9 9″, the output should be “1 0 0 1″.
  9.  
  10. The input is assumed to be an array. Every entry in array represents a digit in input number. Let the array be ‘num[]’ and size of array be ‘n’
  11.  
  12. There can be three different types of inputs that need to be handled separately.
  13. 1) The input number is palindrome and has all 9s. For example “9 9 9″. Output should be “1 0 0 1″
  14. 2) The input number is not palindrome. For example “1 2 3 4″. Output should be “1 3 3 1″
  15. 3) The input number is palindrome and doesn’t have all 9s. For example “1 2 2 1″. Output should be “1 3 3 1″.
  16. 	 */
  17. 	public static void main(String[] args) {
  18. //		for(int i=1;i<10;i++){
  19. //			System.out.println("i= "+i+" "+getMaxPalindromeOfLenthN(i));
  20. //		}
  21. 		int num=0;
  22.  
  23. 		num=999;
  24. 		System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));
  25.  
  26. 		num=1234;
  27. 		System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));
  28.  
  29. 		num=191;
  30. 		System.out.println("num= "+num +" palindrome ="+ getNextHigherPalnidromeNumber(num));
  31.  
  32. 	}
  33. 	public static int getNextHigherPalnidromeNumber(int input){
  34. 		// Handle single digit numbers
  35. 		if(input==9) return 11;     // For 9 next palindrome is 11
  36.  
  37. 		if(input<9) return input+1; // for 0 to 8 next palindrome is next number
  38.  
  39. 		// So now number is two digits or more
  40. 		// Separate out digits 
  41. 		int temp = input;
  42. 		ArrayList<Integer> digitList = new ArrayList<Integer>();
  43. 		while(temp>0){
  44. 			digitList.add(temp%10);
  45. 			temp = temp /10;
  46. 		}
  47. 		// digitList(0) is digit at unit place
  48. 		// digitList(n) will be digit at highest place.
  49.  
  50. 		// Now check if input is equal to max palindrome of that length
  51. 		// In that case next palindrome is min palindrome of lenght+1
  52. 		if(input==getMaxPalindromeOfLenthN(digitList.size())) 
  53. 			return getMinPalindromeOfLenthN(digitList.size()+1);
  54.  
  55. 		// It is not max palindrome of that length. next palindrome is of same length as input.
  56. 		/* if input is 1356 then we will start with first & digit same as input 1 _ _ 1
  57. 		 *  Now we will call same function to get palindrome of internal number by striping first and last digit viz. 35. So function will return 44
  58. 		 *  So answer is 1 4 4 1
  59. 		 *  
  60. 		 *  Now if number is 1996 the we will start with 1 _ _ 1
  61. 		 *  Now we will call same function to get palindrome of internal number by striping first and last digit viz. 99. So function will return 101
  62. 		 *  So it returned palindrome of length more than 2; it means we should increase outer digit
  63. 		 *  2 _ _ 2
  64. 		 *  And we should fill it up with zeros so answer for 1996 is 2002
  65. 		 *  
  66. 		 */
  67.  
  68. 		// Strip first and last digit
  69. 		//  for number 7986  List is -> 6,8,9,7
  70. 		// So starting with digit at index n-2 till index 1; prepare number
  71. 		int outerdigit   =digitList.get(digitList.size()-1);
  72. 		// So 7 _ _ 7   is time being 7007.
  73. 		int returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1) + outerdigit;
  74.  
  75. 		temp = 0;
  76. 		for(int i=digitList.size()-2;i>=1;i--){
  77. 			temp = temp*10 + digitList.get(i);
  78. 		}
  79. 		int palindromeForInnerNumber= getNextHigherPalnidromeNumber(temp);
  80.  
  81. 		// for inner number 99 palindrome will be 101. In this case we should increase higher number and use all zeros
  82. 		// Inner number is of length digitList.size()-2. So palindrome of biggger length id digitList.size()-2+1
  83. 		// For input number 79998 inner number is 999. And its palindrome is 1001. 
  84. 		// Now outer number was decided as 7 and we had prepared temporary palindrome as 7_ _7. So we should make it 8_ _ 8 means 8008
  85. 		if(palindromeForInnerNumber==getMinPalindromeOfLenthN(digitList.size()-2+1)){  
  86. 			outerdigit++;
  87. 			returnVal = outerdigit*(int)Math.pow(10,digitList.size()-1)+ outerdigit;
  88. 		}else{
  89. 			//  For input 7865 palindrome is decided as 7_ _7 i.e. 7007. Inner number is 86. Its palindrome is 99.
  90. 			// Now 99 is to be fit into middle slot. So we will multiply it by 10 and add into number
  91. 			// 7007 + 99*10 = 7007 + 990= 7997
  92. 			returnVal= returnVal+ palindromeForInnerNumber*10 ;
  93. 		}
  94. 		return returnVal;
  95. 	}
  96.  
  97. 	public static int getMinPalindromeOfLenthN(int n){
  98. 		/* For length min palindromes are as follows
  99. 		 * 	 1 1	
  100. 		 *   2 11
  101. 		 *   3 101
  102. 		 *   4 1001
  103. 		 *   5 10001
  104. 		 */
  105. 		// So 1 is present at  10^(n-1) and unit digit
  106. 		// so number is 10^(n-1) + 1
  107. 		if(n==1) 
  108. 			return 1;
  109.  
  110. 		return (int)Math.pow(10, n-1) + 1;
  111. 	}
  112.  
  113. 	public static int getMaxPalindromeOfLenthN(int n){
  114. 		/* For legth max palindromes are as follows
  115. 		 * 	 1 9	
  116. 		 *   2 99
  117. 		 *   3 999
  118. 		 *   4 9999
  119. 		 */
  120. 		int num =0;
  121. 		for(int i=1;i<=n;i++){
  122. 			num = num*10+9;
  123. 		}
  124. 		return num;
  125. 	}
  126.  
  127. }
  128.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
num= 999 palindrome =1001
num= 1234 palindrome =1331
num= 191 palindrome =202
https://ideone.com/3sGpMr
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!