Dual Palindromes
Problem Statement :
A number is called a Dual Palindrome if it's representation in bases B1 and B2 are both palindromes. e.g. LetB1 = 3, B2 = 4, then number 130 (in base 10) will be called a Dual Palindrome, as it is palindrome in base 3 (11211) as well as in base 4 (2002). However, it is not a Dual Palindrome for B1 = 3 and B2 = 5 as it's not a palindrome in base 5(1010).
CodeChef adds this to the problem. Difficulty : Hard
Given two integers B1 and B2, Chef wants to find Dual Palindromes less than 260. If there are more than 1000 Dual Palindromes, then output the first 1000 only (these numbers should be in base 10).
First, we will see how to verify a dual palindrome with 2 bases, then we will generalize the concept to find first 1000 palindromes.
I will break the problem into various tasks and design the functions to get the task done.
BASE CONVERSION
If you had some experience with digital logic and design concepts then you must be familiar with the mathematics behind the concept.
The decimal number is divided by the base in which we want to convert and the remainders are noted down, then we have to reverse the sequence of remainders to get the required number.
Here, I am using an array which stores remainders as we go down but this is the reverse order, so the for loop reverses the order to get the number in the correct order.
Note : In order to reverse the number, i has been started with p, i.e largest index.
Reverse function
In order to check palindrome property we need to reverse the number and check for their equality. For the same the reverse function has been defined.
To reverse the number we need to get individual digits at ones, hundreds, thousand... places, so for that we perform modulo by 10 function which gives us the remainder and that remainder is the digit at ones place and now the digit at ones place must be eliminated as it has already been used, for that reason we divide the number by 10 at each iteration, but after all this when the last bit arrives we get x/10 = 0, hence we cannot get last bit from the loop anymore, so we explicitly get the last bit.
Variables
nb1 ----> Number n in base b1;
nb2 ----> Number n in base b2.
rnb1 ----> Number nb1 reversed
rnb2 ----> Number nb2 reversed
c1 ----> True if nb1 equals rnb1 else False
c2 ----> True if nb2 equals rnb2 else False
That's it, rest of the code is self-explainatory
Thanks for reading!
Link to codechef problem : https://www.codechef.com/problems/DUALPAL
Full C++ implementation/Code :
using namespace std;
int baseConvert(int k, int b) { int p=0; int reversearr[10]; while(k/b != 0) { reversearr[p] = k%b; p++; k = k/b;
} reversearr[p] = k%b; int temp=0; int i; for(i=p; i>=0; i--) { temp = temp*10 + reversearr[i]; }
return temp;
}
int Reverse(int x) { int Sum=0;
while(x/10 != 0) { Sum = 10*Sum + x%10; x = x/10; } Sum = 10*Sum + x%10;
return Sum; }
int main() { int n; int b1,b2; cout<<"Enter the number "; cin>>n; cout<<"Enter base 1 "; cin>>b1; cout<<"Enter base 2 "; cin>>b2;
int nb1,nb2; nb1 = baseConvert(n,b1); nb2 = baseConvert(n,b2);
int rnb1,rnb2; rnb1 = Reverse(nb1); rnb2 = Reverse(nb2);
bool c1 = nb1==rnb1; bool c2 = nb2==rnb2;
cout<<endl; cout<<"The number in base "<<b1<<" is "<<nb1<<endl; cout<<"The reversed number in base "<<b1<<" is "<<rnb1<<endl; cout<<"The number in base "<<b2<<" is "<<nb2<<endl; cout<<"The reversed number in base "<<b2<<" is "<<rnb2<<endl;
if(c1 && c2) { cout<<"The numbers are dual palindrome with respect to "<<b1<<" and "<<b2<<endl; }
else { cout<<"The numbers are not dual palindromes with respect to "<<b1<<" and "<<b2<<endl; }
return 0; }
Sample INPUT/OUTPUT :
n = 130, b1 = 3, b2 = 4
n = 4535, b1 = 3, b2 = 5
Modified code for codechef problem (First thousand dual palindromes).
using namespace std;
int baseConvert(int k, int b) { int p=0; int reversearr[10]; while(k/b != 0) { reversearr[p] = k%b; p++; k = k/b;
} reversearr[p] = k%b; int temp=0; int i; for(i=p; i>=0; i--) { temp = temp*10 + reversearr[i]; }
return temp;
}
int Reverse(int x) { int Sum=0;
while(x/10 != 0) { Sum = 10*Sum + x%10; x = x/10; } Sum = 10*Sum + x%10;
return Sum; }
int main() { int n; cout<<"Enter the number "; cin>>n;
int nb1,nb2; int rnb1,rnb2;
int palindromeCount=0; int b1,b2; for(b1=2; b1<n; b1++) { for(b2=b1+1; b2<n; b2++) { nb1 = baseConvert(n,b1); nb2 = baseConvert(n,b2); rnb1 = Reverse(nb1); rnb2 = Reverse(nb2); bool c1 = nb1==rnb1; bool c2 = nb2==rnb2; if(c1 && c2 && palindromeCount<1000) { cout<<"The number is a dual palindrome with respect to bases "<<b1<<" and "<<b2<<endl; palindromeCount++; }
} } if(palindromeCount<1000) { cout<<"Total possible palindromes "<<palindromeCount<<endl; } else { cout<<"First thousand palindromes"<<endl; }
}
Sample INPUT/OUTPUT :
n = 130
n = 10282
The output is so large, it will take a lot of space so i am attaching the screenshot of beginning and ending of the screen.
Starting:
Ending:
