Yahoo Interview Question
Software Engineer / DevelopersConvert the number to a string - (function usage might be incorrect.. just the algo).
int n = 1224;
char str[10] = {0};
str = itoa(n);
find the middle of the string - we are dividing the string into two parts.
copy each character starting from the last character of the first part to the
first character of second part --
example
two parts --
12 && 24.
copy '2' to '2'
copy '1' to '4'.
str is now -- '1221'
n = atoi(str)
not very efficient but should work.
int closestPalindrome(int num)
{
int len = 0, temp = num;
int closest = 0;
while(temp)
{
temp /= 10;
len++;
}
int i = 1;
temp = num;
while(i<=len/2)
{
int prefix = temp/(pow(10, len-i));
int suffix = temp%(int)(pow(10, i));
num = num + pow(10, --i)*(prefix-suffix);
break;
}
printf("%d\n", num);
}
@keeptrying
Good Try!!!
But i think rather than incrementing the left copy and following the procedure...
U have to copy the right half to the left and follow the same procedure in the second trial.
We have to give the output wrt palindrome not wrt value.
It just my understanding....let me know if i am wrong :)
Shwetank, tell me if I didn't get your solution right.
Let's take 2998 for example. Closest palindrome would be 3003. If we follow ur solution, we will get
2992 - ( for the first step)
9889 - ( or 9999 if we increment left half after copying)
So, in this case we won't get closest palindrome.
None of the solutions provided till now works
This one does. Written in C# and I could do more optimization. But this will give you idea
static string reverse(string w)
{
string z = string.Empty ;
List<char> q = new List<char>();
for (int i = w.Length - 1; i >= 0; i--)
q.Add (w[i]);
foreach (char c in q)
z = z + c.ToString();
return z;
}
static double nearestPalindromicNumber(int x)
{
string z = x.ToString();
int mid = z.Length % 2 == 0 ? z.Length / 2 : (z.Length + 1) / 2;
string w = z.Substring(0, mid );
int mayBe = Convert.ToInt16(w + reverse(w));
double s = 0;
for (double i = x; ; i++)
{
s = Math.Ceiling(i);
if (reverse(s.ToString()).Equals(s.ToString()))
{
if (Math.Abs(x-s) < Math.Abs (mayBe-x))
return s;
}
}
return mayBe;
}
Sorry my last post is incorrect
This one is perfect
-------------------------------
static double nearestPalindromicNumber(int x)
{
string z = x.ToString();
int mid = z.Length % 2 == 0 ? z.Length / 2 : (z.Length + 1) / 2;
string w = z.Substring(0, mid );
int mayBe = Convert.ToInt16(w + reverse(w));
double s = 0;
int far = Math.Abs(x - mayBe);
for (double i = x,loop = 0; loop <=far ; i++,loop ++)
{
s = Math.Ceiling(i);
if (reverse(s.ToString()).Equals(s.ToString()))
{
if (Math.Abs(x-s) < Math.Abs (mayBe-x))
return s;
}
}
return mayBe;
}
KeepTrying, your solution is not only correct, it also finds the correct solution way faster than Sudipta's. Sudipta's solution does brute force checking for the upper palindrome case, while you directly compute it, making yours much faster.
I was just wondering if I missed any special cases for which the pseudo code would not work..
9701 --> Closet Palindrome is 9669, not 9779 based on your solution
You can add 1 to the first half, and also you can deduct 1 from the first half.
Approach: -
1) Check if the number itself is a palindrome
2) If not
initialize count=0, i=1
temp1=number + i
temp2=number - i
a=is_palindrome(temp1) //Returns true if arg IS a palindrome
b=is_palindrome(temp2)
if(!a && !b)
count++;
Repeat (1)
public static void testFindNearestPalindrome(int n) {
class NearPalindromeFinder {
int findNearPalindrome(int start) {
if (testPalindrome(start))
return start;
else {
int neg = start;
int pos = start;
for (int i = 0; i < start; i++) {
if (testPalindrome(start-i)) {
neg = start-i;
break;
}
if (testPalindrome(start+i)) {
pos = start+i;
break;
}
}
return (start == neg) ? pos : neg;
}
}
boolean testPalindrome(int start) {
if (start == 0 || start == 1)
return true;
String str = String.valueOf(start);
String rev = new StringBuffer(str).reverse().toString();
if (str.equals(rev))
return true;
else
return false;
}
}
public static void main(String[] args){
NearPalindromeFinder f = new NearPalindromeFinder();
int palindrome = f.findNearPalindrome(n);
System.out.println("Nearest Palindrome = " + palindrome);
}}
Hi Tim,
How does this work with the class inside a method? Really interested in your coding here though looks really useful :)
Thanks,
Han
Simplified version using the one provided from @Tim.
public class NearestPalindrome {
public static void main(String[] args) {
NearPalindromeFinder f = new NearPalindromeFinder();
int palindrome = f.findNearPalindrome(1299);
System.out.println("Nearest Palindrome = " + palindrome);
}
}
class NearPalindromeFinder {
int findNearPalindrome(int number) {
if (testPalindrome(number))
return number;
int palindrome = number;
for (int i = 0; i < number; i++) {
if (testPalindrome(number - i)) {
palindrome = number - i;
break;
} else if (testPalindrome(number + i)) {
palindrome = number + i;
break;
}
}
return palindrome;
}
boolean testPalindrome(int start) {
if (start == 0 || start == 1) {
return true;
}
String str = String.valueOf(start);
String rev = new StringBuffer(str).reverse().toString();
return str.equals(rev);
}
}
Let me know if there are any test cases failing with it.
Find The Mid Number & then store half number & append it into in reverse order to original.say it a.
2nd subtract 1 from mid of number & append this half number into reverse number to itself. it will show the number that is palindrome thats is less then given number.
say it b.
3rd add 1 to mid of number & then add reverse of this to itself it will represent the number thats palindrome greater then original number
say it c.
now we have to find which is near to original number so basically we have to find the minimum of 3 number.
Note: Need to Review. As This Algorithm Will Suffer With Integer Over Flow
#include
#include
using namespace std;
long long int abs(long long int a)
{
if (a>0)
return a;
return (-a);
}
int count(long long int a)
{
int count=0;
while (a>0)
{
a=a/10;
count++;
}
return count;
}
long long int reverse(long long int a)
{
long long int b=0;
while(a>0)
{
b=b*10+(a%10);
a=a/10;
}
return b;
}
long long int NearestPalindrom(long long int a,int size)
{
long long rev;
if(size%2==0)
rev=reverse(a);
else rev=reverse(a/10);
long long int num=a;
for (int i=0; i num=num*10;
num=num+rev;
return num;
}
int main()
{
long long int a;
cin>>a;
long long int num=a;
int sizea=count(a);
for(int i=0; i num=num/10;
long long int pa = NearestPalindrom(num,sizea);
long long int pb = NearestPalindrom(num-1,sizea);
long long int pc = NearestPalindrom(num+1,sizea);
int da,db,dc;
da=abs(pa-a);
db=abs(pb-a);
dc=abs(pc-a);
if (da cout< if (db cout< if (dc cout<
}
Algorithm:
1) Convert the number to a string.
2) Take the substring from the start to the middle digit. Reverse that substring and append it to the result = substring(0,n/2) + reverseOf(subString(0,n/2))
3) Convert it back to integer.
4) If this number is less than the number, add 1 to the substring from 0 to n/2 and repeat the reverse and append process. If greater, subtract one and do the reverse and append.
5) Now you have the possible closest 2 palidromes.
Return the one which has a minimum distance from the original number
pseudo code: (with two examples in parentheses)
There can be better way. This is just the first answer I came up with. :)
- KeepTrying November 01, 2009