kumsaha
BAN USERvoid longestdistance(node **head)
{
node *p=*head;
int countleft=1,countright=1;
while(p->left!=NULL || p->right!=NULL)
{
while(p->left!=NULL)
{
p=p->left;
countleft++;
}
if(p->left==NULL && p->right!=NULL)
{
p=p->right;
countleft++;
}
}
p=*head;
while(p->left!=NULL || p->right!=NULL)
{
while(p->right!=NULL)
{
p=p->right;
countright++;
}
if(p->right==NULL && p->left!=NULL)
{
p=p->left;
countright++;
}
}
cout<<countleft<<" "<<countright<<endl;
cout<<(countleft+countright-1);
}
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<
}
O(n)
first create an array of m elements(for this question m is 50)
in a single scan select the elements out of order from the main array and copy it into side array and simulataneously shift the right hand side elemets to the left which might take maximum of O(n).
then sort the newly created array using may be quicksort O(m log m),
then apply merging from back which can be done in O(n)
therefore totaly time taken would be O(n + n +m log m+n)
unless and until m is of the order of n
the above expresion reduces to O(n).
@anjana
- kumsaha November 21, 2012In the algo presented by The Artist
a minor modification is needed such that it doesnt take into account of the words such as (sumit with sumitas)
what we can do is make the changes in that space i.e O(26)
for example the word sumit has to be searched
so s-1,u-1,m-1,i-1,t-1
when the word sumita is encountered all the fields in O(26) is zero except a which is -1,
so this is our word.
now if we take sumi , then only value corresponding to field t is -1.
but if we take a word such as samit then field corresponding to u would be 1 and a would be -1,
in a iteration corresponding to the word length there can be only a pair of 1 & -1;
we wont consider if there is 1&1 or -1 & -1 which might arise in the example of (umi or sumitaf) which would be the case for difference in length corresponding to 2.