Amazon Interview Question
Software Engineer / DevelopersCountry: India
your solution is wrong...
check for this one
126 1 521
3 0 1.....etc ...ur solution will always give the wrong answer..try to think lil bit more..if u wont get correct solution then i'll tell you.. :)
Thanks @Shishivicto! I forget to add the following line. Thanks for pointing it.
For case 1 and 3( if first half is less than second half) reverse first half number and convert to a number, and then check whether it is bigger than second half. If bigger, then just reverse and paste it at right side and we don't need of adding 1 with it. Otherwise, for both cases add one and do as wrote above.
eg:
126 521==> we can just reverse first half and paste it at right side
126 1 521 ==> we can just reverse first half and paste at right side
Another case needs to be addressed where first hal and second half are equal, like 747.
Also
for 123 301 it gives 124 421 whereas expected is 123 321
for 856 714 it gives 856 658 whereas expected is 857 758
for 123 1 301 it gives 123 2 321 whereas expected is 123 1 321
for 856 1 714 it gives 856 1 658 whereas expected is 856 2 658
Crux is that you should compare the reverse of first half with secod half rather than comparing first half with second half..
Also put a precheck for
-all 9s if it's so just add 2 to number
-single digit : just add 1 to number
Yea, we all realize that there are some mistakes in BVarghese's solution, but he is basically on the right track. Cut him slack and figure out the edge cases yourself.
I feel BVargese need to correct just a bit. instead of comparing first half with second, we need to compare reverse of first half with second. If the reverse of first half is greater, we just have to paste it as such. Otherwise, if the reverse of first half is smaller, add one to the original, reverse and then paste.
eg:
4135: reverse(41) = 14 < 35. So, 41+1=42, reverse(42) = 24. So, 4224 is the answer.
41935: 419+1=420. So, 42024 is an answer.
I feel all cases are included now.
void FindTheNextPalindrom(int n){
while(true){
n++;
if(n>Integer.MAX_VALUE){
System.out.println("the number is too large");
break;
}
if(isPalindrom(n)){
System.out.println(n);
break;
}
}
}
public static boolean isPalindrom(int n){
ArrayList<Integer> digits=new ArrayList<Integer>();
while(n!=0){
digits.add(n%10);
n=n/10;
}
for(int i=0;i<digits.size()/2;i++){
if(digits.get(i)!=digits.get(digits.size()-1-i)){
return false;
}
}
return true;
}
// I tested all examples above. worked for all XD
int main(void)
{
int n;
int count = 0;
int div;
int *str = new int[256];
int pad = 0;
cin >> n;
div = n;
while ( div > 0)
{
str[count++] = div%10;
div /= 10;
}
count --;
for (int i = 0; i < (count+1)/2; i++){
if ( (str[i] + pad) <= str[count - i]){
pad = 0;
}
else{
pad = 1;
}
str[i] = str[count-i];
}
if (count%2 == 0 && pad ==1){
if (str[count/2] < 9)
str[count/2] ++;
else{
str[count/2] = 0;
str[count/2+1] ++;
str[count/2-1] = str[count/2+1];
}
}
if (count%2 == 1 && pad == 1)
{
str[int(count/2) +1] ++;
str[int(count/2) ] = str[int(count/2) +1 ];
}
for (int j = 0; j <= count; j++)
cout << str[j];
cout << endl;
return 0;
}
Code in JAVA
public int nextLargestPalindrome(int number)
{
int length = String.valueOf(number).length();
boolean oddDigits = (length % 2) != 0;
String leftHalf = getLeftHalf(number);
String middle = getMiddle(number);
int increment;
int newNum;
if(oddDigits)
{
increment = (int)Math.pow(10, length/2);
newNum = Integer.parseInt(leftHalf + middle + reverseIt(leftHalf));
}
else
{
increment=(int)(1.1*Math.pow(10, length/2));
newNum = Integer.parseInt(leftHalf + reverseIt(leftHalf));
}
if(newNum > number)
return newNum;
if(!middle.equals("9"))
{
return newNum + increment;
}
else
{
return nextLargestPalindrome(roundUp(number));
}
}
private int roundUp(int number)
{
int length = String.valueOf(number).length();
int increment = (int)Math.pow(10, length/2 + 1);
return ((number/increment) + 1) * increment;
}
private String getMiddle(int number)
{
String str = String.valueOf(number);
return Character.toString(str.charAt(str.length() / 2));
}
private String getLeftHalf(int number)
{
String str = String.valueOf(number);
return str.substring(0, str.length() / 2);
}
public static String reverseIt(String a) {
int length = a.length();
StringBuilder reverse = new StringBuilder();
for(int i = length; i > 0; --i) {
char result = a.charAt(i-1);
reverse.append(result);
}
return reverse.toString();
}
We can write a simple program for the following 4 cases, which will be answer for this question.
- BVarghese January 09, 2012There are two main cases. 1. Number of digits is odd. 2. Number of digits is even.
In odd case, it has to be separated into three groups. 1. First half 2. Middle digit 3. Second half.
In even case, it has to be separated into two groups. 1. First half 2. Second half.
Now consider following different cases.
1. Case 1: Even number of digits and first half is less than second half.
123 456 124 421
Add 1 to first half, reverse first half and paste it at right side.
2. Case 2: Even number of digits and first half is greater than second half.
456 123 456 654
Just reverse it and paste it at right side.
3. Case 3: If odd number of digits and first half is less than second half.
123 1 234 123 2 321
Add 1 to combined first half and middle one (here 1231+1). Then separate middle one and reverse first half and paste it on right side
Another example: 123 9 234 124 0 421 (here 1239 +1= 1240).
4. Case 4: If odd number of digits and second half is less than second half.
445 9 123 445 9 544
Reverse first half and paste it on right side