Adobe Interview Question Member Technical Staffs
Team: Live Cycle
Country: United States
Interview Type: In-Person
How can H have more digits then L?
H having more digits then L is only possible when L is 99 / 999/9999...
and if L = 99 then R can never be greater than reverse(L) as max value can be 99 itself.
so any number like 99ab next greater palindrome will be 9999 except when n = 9999 in that case.
H = "If H has more digits than L then H.append(reverse(H / 10)) else H.append(reverse(H)) will be the answer."
should not work according to me.
Please correct me if I am wrong.
You want the next palindrome number which comes after given number ?
OR
The next higher palindrome number that can be formed using digits of give number ?
I did this algo -
Case 1 - Number length is even
Step 1 - Divide number in two equal halfs. Call left one as L, right one as R.
Step 2 - Check if R <= reverse of L. If it is put R = reverse of L. Print number
Step 3 - else if R > reverse of L. Increment L by 1. Make R = reverse of L. Print number.
Case 2 - Number is of odd length
Step 1 - Divide number in 3 parts call them as L (Left), M (Middle), R (Right) . M will always have single integer.
Step 2 - Check if R is <= reverse of L. Make R = reverse of L. Print number.
Step 3 - else if R > reverse of L.
Step 4 - check if M < 9
Step 5 - M++. Make R = reverse of L. Print number.
Step 6 - else Make M = 0, Increment L by 1. Make R = reverse of L. Print number.
---------------------------------------
But interviewer seems to be un-satisfied. What is wrong in this algo. I could not find anything wrong in this.
As long as he will only replace R by L, but not L by R, I don't think 4049 will return 9449.
But just I doubt, if a palindrome number is given as input, this algo will always return the input only.
@tom.thkwok - I think i got your point this algo will return same no if input is itself palindrome..so instead of checking for <= check only for < and handle = case differently.
Case 1 - if number is of even length
If R = reverse of L. Increment L by 1. R = reverse of L. Print no.
Case 2 - If number is of odd length
If R = reverse of L.
If M < 9
Increment M. Print no.
else
M = 0, Increment L by 1. R = reverse of L. Print no.
----------------------
But interviewer did not present this counter example and at that time it did not came up in my mind. He was giving no hint of what he wanted and where I was wrong. At least one counter example would have served better.
@nitingupta180, Follow the below link::
geeksforgeeks.org/archives/23497
It has a well explanation.
for even number case if gievn number is palindrome at that time your last condition will fail.
Alog should be
Step 1 - Divide number in two equal halfs. Call left one as L, right one as R.
Step 2 - Check if R < reverse of L. If it is put R = reverse of L. Print number
Step 3 - else if R >= reverse of L. Increment L by 1. Make R = reverse of L. Print number
int* palindrome(int n, int l)
{
int j=0,k[l];
for(;j<l;j++)
{
k[j]=(n%10);
n=n/10;
}
if(l%2==0)
{
if(k[(l/2)]>k[(l/2)-1])
{
for(j=0;j<l/2;j++)
{
k[j]=k[l-j-1];
}
}
else
{
k[(l/2)]++;
for(j=0;j<l/2;j++)
{
k[j]=k[l-j-1];
}
}
}
else
{
if(k[(l/2)]>k[(l/2)-1])
{
for(j=0;j<l/2;j++)
{
k[j]=k[l-j-1];
}
}
else
{
k[(l/2)]++;
for(j=0;j<l/2;j++)
{
k[j]=k[l-j-1];
}
}
}
for(j=0;j<l;j++)
{
printf(" %d ",k[j]);
}
return k;
}
void FindNextHigherPalindrom(int piValue)
{
int lstrValue[15];
int liIndex=0;
for(int liTempValue=piValue;liTempValue;liIndex++)
{
lstrValue[liIndex]=liTempValue%10;
liTempValue/=10;
}
if(lstrValue[liIndex/2]<=lstrValue[liIndex/2-1])
{
if(lstrValue[liIndex/2]==9)
{
int liLocal;
for(liLocal=liIndex/2;lstrValue[liLocal]==9&&liLocal<liIndex;liLocal++)
{
lstrValue[liLocal]=0;
}
if(liLocal==liIndex)
{
lstrValue[liIndex++]=1;
}
else
{
lstrValue[liLocal]++;
}
}
else
{
lstrValue[liIndex/2]++;
}
int liLocal;
if(liIndex%2==0)
{
liLocal=liIndex/2-1;
}
else
{
liLocal=liIndex/2;
}
for(int liLocal1=liIndex/2;liLocal>=0;liLocal--,liLocal1++)
{
lstrValue[liLocal]=lstrValue[liLocal1];
}
}
for(int i=0;i<liIndex;i++)
cout<<lstrValue[i];
}
let me know if there is any bug in this
#include <vector>
void numToDigitVec(int n, std::vector<int>& digits)
{
digits.clear();
int div = 10;
while (n > 0)
{
digits.push_back(n % div);
n /= 10;
}
}
int digitVecToNum(std::vector<int>& digits)
{
int n = 0;
int mul = 1;
for (size_t i = 0; i < digits.size(); ++i)
{
n += mul * digits[i];
mul *= 10;
}
return n;
}
int next_palin(int n)
{
std::vector<int> digits;
numToDigitVec(n, digits);
size_t j = digits.size();
size_t mid = j/2;
for (size_t i = 0; i < digits.size()/2; ++i)
{
if (digits[j-mid+i] > digits[mid-i-1])
{
digits[mid-i-1] = digits[j-mid+i];
}
else
{
digits[j-mid+i] += 1;
digits[mid-i-1] = digits[j-mid+i];
}
}
int res = digitVecToNum(digits);
return res;
}
initially was thinking about set creation, dropped it immediately. Now algo is as follows
if ( r > l )
if ( odd.no.of.ele)
increment ( mid )
else
increment ( l )
r = reverse ( l )
Say the given number n has d digits.
If d is even:
1. Find the left and right halves of the number (say L and R).
2. If reverse(L) > R then L.append(reverse(L)) is the answer.
3. Else calculate H = L + 1
4. If H has more digits than L then H.append(reverse(H / 10)) else H.append(reverse(H)) will be the answer.
If d is odd:
1. Find the left and right halves of the number both including the middle digit (say L and R)
2. If reverse(L) > R then L.append(reverse(L / 10)) is the answer.
3. calculate H = L + 1
4. If H has more digits than L then (H / 10).append(reverse(H / 10)) else H.append(reverse(H / 10)) will be the answer.
Note: reverse should preserve the leading zeros and division is an integer division
import java.util.Arrays;
public class NextPalindrome {
public static void main(String[] args) {
// TODO Auto-generated method stub
int i=9999;
System.out.println("the next number which is palindrome is:"+nextHigherPalindrom(i));
}
private static int nextHigherPalindrom(int i) {
// TODO Auto-generated method stub
String originalNumber=i+"";
char[] numberArr=originalNumber.toCharArray();
int originalLength=numberArr.length;
char[] leftPart=Arrays.copyOfRange(numberArr, 0, originalLength/2);
String optionalMidPart=originalLength%2==0?"":originalNumber.charAt(originalLength/2)+"";
char[] rightPart=originalLength%2==0?Arrays.copyOfRange(numberArr, originalLength/2, originalLength):Arrays.copyOfRange(numberArr, (originalLength/2) +1,originalLength );
int leftLength=leftPart.length;
for(int index=0;index<leftLength;index++)
{
rightPart[leftLength-index-1]=leftPart[index];
}
String newOne=new String(leftPart) + optionalMidPart + new String(rightPart);
if(Integer.parseInt(newOne)<= Integer.parseInt(originalNumber))
{
int lPos=leftPart.length-1;
int rPos=0;
if(originalLength%2!=0)
{
optionalMidPart=Integer.parseInt(optionalMidPart)+1+"";
optionalMidPart=optionalMidPart.substring(0,1);
newOne=new String(leftPart) + optionalMidPart + new String(rightPart);
}
while(Integer.parseInt(newOne)<= Integer.parseInt(originalNumber) && lPos>=0)
{
String lStr=( (Integer.parseInt(leftPart[lPos]+"")+1)%10) + "";
String rStr=((Integer.parseInt(rightPart[rPos]+"")+1)%10) +"";
leftPart[lPos]=lStr.charAt(0);
rightPart[rPos]= rStr.charAt(0);
newOne=new String(leftPart) + optionalMidPart + new String(rightPart);
lPos--;
rPos++;
}
if(Integer.parseInt(newOne)<= Integer.parseInt(originalNumber))
{
newOne="1"+newOne +"1";
}
}
return Integer.parseInt(newOne);
}
}
Say the given number n has d digits.
- Naveen Reddy Mandadi October 20, 2012If d is even:
1. Find the left and right halves of the number (say L and R).
2. If reverse(L) > R then L.append(reverse(L)) is the answer.
3. Else calculate H = L + 1
4. If H has more digits than L then H.append(reverse(H / 10)) else H.append(reverse(H)) will be the answer.
If d is odd:
1. Find the left and right halves of the number both including the middle digit (say L and R)
2. If reverse(L) > R then L.append(reverse(L / 10)) is the answer.
3. calculate H = L + 1
4. If H has more digits than L then (H / 10).append(reverse(H / 10)) else H.append(reverse(H / 10)) will be the answer.
Note: reverse should preserve the leading zeros and division is an integer division