Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
how about 999?
1. mid = 9 @ index 1.
2. make mirror on the right side of mid. it gives 999.
3. increment mid by 1. it gives 1009.
as the number of digits have changed, we repeat the algo again? (gives 1001 which is correct!!)
sound promising with small change that we need to copy [left->mid] elements to [mid->right] in reverse order.. Here we are starting from mid (not from mid+1 as mentioned in original post) till right..
For 999 case,
middle element is 9,
9+1=10 so increment the next number which is 9
so now the number becomes 1009..
left->mid contents [10]
copy these in reverse order from [mid->right]
so final result is 1001
1001>999 so the next palindrom is 1001...
Hope this helps..
A palindrome can be of odd length or even length.
So if the given number is odd:
ex: 98099
1. if the reverse of the first of the palindrome is > the second half then the next palindrome = first half + middle number + reverse(first half) where + means concatenation. Otherwise go to step 2. For 98099, 89 < 99 so move to step 2
2. If the middle number is not 9, then increment the middle by 1 to get the new new middle, and the second half is the reverse(first half). Otherwise go to step 3
For 98099 this becomes 98189 so you're done
3. If the middle number is 9, set the new middle to 0, increment first half by 1, and reverse the new first half by 1 to get the second half. concatenate them all and you're done.
The is for cases like 96997 => 97079
Even case is easily derivable from the odd case. I leave that as an exercise for the reader
Hi Augustine,
Your solution is correct. I also worked it out, and it seems like the simplest solution. The solution for the Even # of digits case is even easier as you don't have to find a pivot, you just keep increasing the mirror(firstHalf) number by one until it's >= second half. Then replace the second half with it.
I was initially just increasing the value of the mirror half by 1. It works but it can be faster if you compare each digit in the mirror and second halves from left to right so if you have:
502343, you split the halves and reverse the first one:
205 and 343.
205 < 343, and 2 < 3, so you make 2 into 3
Now you have 305 and 343. 305 < 343, and 0 < 4, so you make that 0 into a 4.
You now have 345 > 343, and then you can replace the second half with 345 to get the next palindrome: 543345
If the # of digits is Odd, it works the same, except you take the pivot out and make it zero.
5027343 would become two halves like above 205 and 343, leaving the pivot out and also making it zero. you end up with 5430345, and then the pivot just increases by 1 in a loop if one wants:
for(int i=0; i < 9; i++)
println(firstHalf.toString + (pivot+i) + secondHalf.toString);
.
So this solution can be improved by not comparing the entire RHS with the reversed LHS. Because one increment in LHS automatically makes the number way higher than the previous number. So the moment 2 is incremented to 3...we can stop.and copy the LHS.
Or going back to Augustines solution, we can check the middle digits...like 502343 the nearest palindrome is 502205...but since its lesser we increment the middle pair.
Please correct me if i'm wrong
1. Reach the middle point of number, (if total number of digits are odd, middle number is the pivot, else better to insert a 0 and make the number of digits odd and proceed, and don't forget to remove it while comparing or in final product)
2. Copy the left side of pivot to right side in reverse order
3. If the resultant is greater than the given, then done,
4. If not, then increase both the digits with smallest distance from pivot
5. Continue untill it's greater than given number
6. If 1~(9-digit) failed, then proceed with the next smallest distance digit (yet to find such example)
Dude Check out for the case
8999. palindrome should be 9009.. and in this case you have to play with a carry
whenenver u move to next smallest distance digit from the pivot and increase it, then you should make all the digits between the pivot and the current digit as 0
public void pali(int num){
int x = num;
while(true){
int rev = 0;
int n = x;
for (int i=0; i<=n; i++){
int r=n%10;
n=n/10;
rev=rev*10+r;
i=0;
}
if(x == rev){
System.out.print("Next palindrome number : " + rev);
break;
}
x++;
}
}
1. For a input, e.g., 301, find its highHalf. In this case, it is 30.
2. Cal lowHalf based on highHalf. Since the len of 301 is odd, the lowHalf is 30 / 10 = 3 in our case. If the len of the input is even, e.g., the lengh of 12 is 2, then the lowHalf is the same as highHalf.
4. Calc highHalf * pow(10, halfLen) = lowHalf
5. repert 4. The first number which is greater or equal to the input is what we want.
The code:
unsigned int FindPalindrome(unsigned int input)
{
int temp = input;
int len = 0;
while(temp > 0)
{
temp /= 10;
++len;
}
if(len == 0 || len == 1)
return input;
int halfLen = len / 2;
int highHalf = input;
for(int i = 0; i < halfLen; ++i)
{
highHalf /= 10;
}
while(true)
{
int lowHalf = highHalf;
if(len % 2 == 1)
lowHalf /= 10;
unsigned int ret = highHalf;
for(int i = 0; i < halfLen; ++i)
{
ret *= 10;
}
ret += lowHalf;
if(ret >= input)
return ret;
++highHalf;
}
}
If we take note that a palindrome must be mirrored, then we can deduce that the next largest palindrome would be one with its central most digit incremented. This can be derived from the fact that the next largest (not necessarily palindrome) number is one with its LSD (least significant digit) increased by 1, however since we need to retain it as a palindrome it also means the MSD will need to be increased also - which is far from optimal. You can observe from this that the most optimal strategy would be to increase the center digits due to the mirror-like property of palindromes. From the example above, if we incremented the first (and consequently last) digit then we yield 2552, however this isn't the most optimal step because you can modify the central digits to 1661 and retain palindrome status.
So we have a basic strategy but it isn't complete. What happens if the center digits happened to be 9's? You set the currently operating digits to be 0 and increment the next pair of digits as this yields the next smallest number. For example, given 1999 - you first mirror it to 1991, increment the center digits to yield 1001 and then increment the next set of digits to yield 2002 - which is the expected answer. This obviously needs to be looped via iteration or called recursively for multiple 9's.
So are we done yet? Not quite. There is still one minor case we need to cover, it's one that reaches to the MSD but still needs to "carry on" the increments or more simply "all 9's". A basic example would be 9999, if you do the algorithm above then you end up yielding 0000 and still need to increment 1 to the next set of digits (which don't exist as of yet). Covering this case is rather simple, add an extra digit '1' to the beginning of the number (i.e. 0000 -> 10000) and change the LSD to a 1 also (for obvious reasons).
The first sentence says "...we can deduce that the next largest palindrome would be one with its central most digit incremented". I admit I haven't read the whole paragraph enough times, but I wonder whether that statement is true already given numbers like 23123, where the next palindrome should be 23132, where the middle digit (1) didn't need to be incremented.
Here is my logic:
Start from the leftmost and rightmost digit. Consider them as locations as left and right.
Until both left and right either become equal or cross each other, do the following
1. Increment the left until it becomes equal to right
2. Move left to right and right to left.
this approach will give a palendrom but not the next palendrom
for Ex 103 when we increment left till it become equal to right. it becomes 303
bot ans should be 111
True.
I have changed the approach. I think comparing with its reversal is one of the best.
Here is the code:
// Find the next palindrome number which is greater than or equal to a given number
// For example, given number is 1235, then next palindrome number is 1331.
// Approach is if number - reverse of number == 0, then number is palindrom. Hence we will keep increasing the number till it meets the condition.
#include <iostream>
#include <math.h>
using namespace std;
int Reverse(int n)
{
if (n < 0)
{
throw exception();
}
int temp = 0;
// first calculate number of digits
int power = 0;
int num = pow(10, power);
while (n / num != 0)
{
power++;
num = (int)pow(10, power);
}
int rem = 0;
// now use modulo operator to reverse the number
for (int i = 0; i < power; i++)
{
temp += (n % 10) * (int)pow (10, power-i-1);
n = n / 10;
}
return temp;
}
int main()
{
int n = 3221;
while (n - Reverse(n) != 0)
{
cout << "Current number is: " << n << endl;
n++;
}
cout << n << endl;
n = 1235;
while (n - Reverse(n) != 0)
{
cout << "Current number is: " << n << endl;
n++;
}
cout << n << endl;
return 0;
}
Pseduo code -
Take two pointer A and B .
A points to MSB
B points to LSB
while(A and B are not crossed and are not equal)
{
if(Value(@A)>Value(@B))
replace value @B with value @A;
move B by 1 step towards MSB(towards Right) and move A by 1 step towards LSB(towards Left)
if(B is not pointing to A)
increment value @B by 1, and propagate the carry as normal ,but during propagation any
changes made to values pointing after A(i.e right side), should reflect the same values
pointing after B(i.e left side)
else
replace value @B with value @A;
move B by 1 step towards MSB(towards Right) and move A by 1 step towards LSB(towards Left)
}
Eg: take 6989
A->6 and B->9
since A < B
replace value @B by a i.e 9 by 6. so now value ll be 6986.
move A and B by 1 step , so A -> 9 and B->8,
increment B by 1 (coz A>B before move was done)
so value ll be 6996.
now A->9 and B-> 9
since A==B,else part ll be executed
so replace Value @B by Value @A , move A and B by 1 step
now A and B are crossed so come out of the loop
so new value ll be the nearest palindrome.
<pre lang="" line="1" title="CodeMonkey43182" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
int num=r.readInt();
num++;
while(isPalindrome(num)==false)
{
num++;
}
System.out.println(num);
}
public bool iSPalindrome(int num)
{
int rev=0;
while(num>0){
int cur= num%10;
rev= rev*10+cur;
num= num/10;
}
return num-rev==0;
}
}
</pre><pre title="CodeMonkey43182" input="yes">125</pre>
public class stringPalindrome
{
public static void main (String[] args) throws java.lang.Exception
{
// java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
int num=999;
num++;
while(isPalindrome(num)==false)
{
num++;
}
System.out.println(num);
}
public static boolean isPalindrome(int num)
{
int rev=0;
int oringalNum=num;
while(num>0){
int cur= num%10;
rev= rev*10+cur;
num= num/10;
}
return oringalNum-rev==0;
}
}
if digits odd
{
Place mirror of MSBs in LSB
If number < transformed number return
Increment pivot by 1 and place mirror of MSBs in LSB
}
else
{
Place mirror of MSBs in LSB
if number < transformed number return
Increment the least significant bit of MSBs by 1 and place mirror of MSBs in LSB
}
Consider a example:
Case 1: for odd number of digit:
a) 12345
ans a) Find the middle number. Iterate from beginning and put the digits on right
like: 12321
and increase the middle number by 1
so the next palindrome is 12421
Case ii:
Consider example if the number 123456
Leave the middle two numbers such as 3, 4 here
Iterate from beginning and put the number at the end such as:
123421
Now increase the first middle number by 1 and put the same number at the second middle number
so ans is: 124421
I think you should compare numbers after calculating..
And for 891.see below
891->191 so neglected
891->898 first answer
891->901 now find for 901 and compare it with 898.
now for 901 next palindrome will be 909 and 898 is smaller than 909 so 898 is the answer.
yeah there are basically 4 rules to find the next palindrome.
They can best be described using examples:
num -> next palindrome
35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35911 -> 36063 (increment and mirror the upper half)
99965 -> 100001 (special case)
hence, what we need to do is just to check all of them in the order they listed above. The code is as follows:
// finds a smallest palyndrome number x2 > x
int next_palyndrome(int x) {
int digits[12], n, x2 = x;
for(n = 0; x2 != 0; n++) {
digits[n] = x2 % 10;
x2 /= 10;
}
int n2 = n / 2, n2p1 = n2 + (n & 1);
// first try replacing the lower digits with rev upper digits
int rev_hi = digits[n2p1], exp = 10;
for(int i = 1; i < n2; i++) {
rev_hi = rev_hi * 10 + digits[n2p1 + i];
exp *= 10;
}
int hi = x / exp, lo = x % exp; // extract lower and upper halves
x2 = hi * exp + rev_hi;
if(x2 > x) // CHECKING RULE 1
return x2;
hi += 1; // increment 'hi' and construct the number again
if(hi == exp) { // handle a special case when hi = '99...99'
if(n & 1) { // here we return: 100..001
x2 = hi * exp * 10 + 1;
} else {
x2 = hi * exp + 1;
}
return x2; // CHECKING RULE 4
}
int t = (n & 1) ? hi / 10 : hi; // divide out a middle digit if necessary
rev_hi = t % 10;
// calculate the reverse of 'hi' again
for(int i = 1; i < n2; i++) {
t /= 10;
rev_hi = rev_hi * 10 + (t % 10);
}
x2 = hi * exp + rev_hi;
return x2; // RULE 2 and 3 (together)
}
int main() {
int x = 4992734;
while(1) {
printf("next: %d\n", x);
int x2 = next_palyndrome(x);
if(x2 <= x) {
printf("FATAL: %d %d\n", x2, x);
break;
}
x = x2;
}
return 1;
}
sample output:
next: 4992734
next: 4992994
next: 4993994
next: 4994994
next: 4995994
next: 4996994
next: 4997994
next: 4998994
next: 4999994
next: 5000005
next: 5001005
next: 5002005
next: 5003005
next: 5004005
next: 5005005
next: 5006005
next: 5007005
next: 5008005
next: 5009005
next: 5010105
next: 5011105
next: 5012105
next: 5013105
next: 5014105
next: 5015105
next: 5016105
next: 5017105
next: 5018105
next: 5019105
next: 5020205
next: 5021205
next: 5022205
next: 5023205
next: 5024205
next: 5025205
num -> next palindrome
35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35911 -> 36063 (increment and mirror the upper half) - wrong should be 35953
99965 -> 100001 (special case) - Wrong should 99999
you are right, sorry I've just chosen the wrong examples
but the rules are correct. It should be:
35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35972 -> 36063 (increment and mirror the upper half)
99999 -> 100001 (special case)
anyway it does not make the algorithm wrong
public int next_Palindrom(int input){
char[] input_int = new Integer(input).toString().toCharArray();
boolean x = next_Pal(input_int,0,input_int.length-1);
if(x){
return new Integer(new String(input_int)).intValue();
}else{
// the case 99...99;
return new Integer(new String(input_int)+2).intValue();
}
}
There are two variances to generate next palindrom given input[bgn] and input[end]:
a) if input[bgn] > input[end] do input[end] = input[bgn]. -easy case
b) if input[bgn] <= input[end] (such as '1'22'3' or '1'2'1') we call next_Pal() on bgn+1,end-1. If sub-routine returns true this means that somewhere in the inner string carry the next palindrome (e.g. '1'33'1' or '1'3'1'). All you need now is to equalize left wing and right wing. If it returns false (e.g. '1'9'1' or 1'2'<null>'2'1 then we increments input[bgn] and set input[end] = input[bgn], then zeroOut all input[bgn+1,end-1] (e.g. 202 or 1331). Then return true if the next palindrome is generated within input[bgn,end] and false if otherwise.
protected boolean next_Pal(char[] input_str,int bgn,int end)
{
//base case
if(bgn > end)
return false;
//case #1
if(input_str[bgn] > input_str[end]){
input_str[end] = input_str[bgn];
return zeroOut(input_str,bgn+1,end-1);
}else{
//case #2
if(next_Pal(input_str,bgn+1,end-1)){
input_str[end] = input_str[bgn];
return true;
}else if(input_str[bgn] != '9'){
input_str[end] = input_str[bgn] = (char)(input_str[bgn] + 1);
return zeroOut(input_str,bgn+1,end-1);
}else
return false; //the case 99...9
}
}
private boolean zeroOut(char[] input_str, int bgn, int end) {
while(bgn < end){
input_str[bgn++] = input_str[end--] = '0';
}
return true;
}
A palindrome can be of odd length or even length.
So if the given number is odd:
ex: 98099
1. if the reverse of the first of the palindrome is > the second half then the next palindrome = first half + middle number + reverse(first half) where + means concatenation. Otherwise go to step 2. For 98099, 89 < 99 so move to step 2
2. If the middle number is not 9, then increment the middle by 1 to get the new new middle, and the second half is the reverse(first half). Otherwise go to step 3
For 98099 this becomes 98189 so you're done
3. If the middle number is 9, set the new middle to 0, increment first half by 1, and reverse the new first half by 1 to get the second half. concatenate them all and you're done.
The is for cases like 96997 => 97079
Even case is easily derivable from the odd case. I leave that as an exercise for the reader
<pre lang="" line="1" title="CodeMonkey48795" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
</pre><pre title="CodeMonkey48795" input="yes">
</pre>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "StdAfx.h"
#include<locale.h>
#include <iostream>
using namespace std;
int main()
{
char a[1000002];
int test,i,f,fp,l,mid;
scanf("%d\n",&test);
while(test--)
{
f=1;
gets(a);
l=strlen(a);
fp=0;
for(i=0;i<l;i++)
{
if(a[i]!='9')
{
f=0;
break;
}
}
if(f==1)
{
a[0]='1';
for(i=1;i<l;i++)
a[i]='0';
a[l]='1';
a[l+1]='\0';
fp=1;
}
f=0;
if(fp!=1)
{
for(i=0;i<l/2;i++)
{
if(a[i]<a[l-1-i])
f=-1;
else if(a[i]>a[l-1-i])
f=1;
a[l-1-i]=a[i];
}
if(l%2==0)
mid=l/2-1;
else mid=l/2;
if(f==0||f==-1)
{i=0;
while(a[mid-i]=='9')
{
a[mid-i]='0';
a[l-1-mid+i]='0';
i++;
}
a[mid-i]++;
a[l-1-mid+i]=a[mid-i];
}
}
printf("%s\n",a);
}
return 0;
}
the following code (in Java) works
public static boolean isPallindrome(int number){
int original = number;
int units=0;
int result=0;
while (number > 0){
units= number%10;
result = result * 10 + units;
number = number / 10;
}
return (original == result)? true : false;
}
public static int findNextPallindrome(int number){
int temp=0;
for(int i=1;i<2000;i++){
temp = number + i;
if(isPallindrome(temp)){
return temp;
}
}
return -1;
}
This has a time complexity of O(n). That can be done in O(log n) (to the base 10) by using the following logic
1. For even numbers make two halves lefthalf and righthalf
2. reverse left half reverseleft
3. if reverseleft<=righthalf
4. answer is lefthalf+1 +reverse of(left half+1)
5. else if reverseleft>right half answer is lefthalf+reverse of(left half)
for odd the above strategy will hold with only exception that middle digit will be included in both left and right half
And during answer also the middle digit will be merged
See complete java code here
See my below post for code link
Reach the middle digit of num, say it is mid.
- Srikant Aggarwal November 18, 2011Increment it by 0, 1, 2.... .
If there is a carry over than increment the digit before it.Copy the from start to mid to digits after mid in reverse order.
At any instant the resultant no comes out to be greater than original no, stop the operation.
For eg: 394
mid = 9
9+0 = 9 393 < 394
9+1 = 10 inc 3->4 404 > 394
So 404.
3836
mid = 8
8+0 = 8 3883 > 3836
So 3883
Please provide your valuable suggestions.