#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
typedef unsigned long long BigDataType;
bool isPalindrome(const string& value){
int begin = 0;
int end = value.size() - 1;
while(begin < end){
if( value[begin++] != value[end--] ) return false;
}
return true;
}
template<typename Type>
string convertToString(const Type& num){
stringstream ss;
(ss << num);
return ss.str();
}
string getBase(BigDataType num, const unsigned int& toBase, const char * baseValue)
{
string baseNum = "";
while(num > 0){
baseNum += baseValue[num % toBase];
num /= toBase;
}
std::reverse(baseNum.begin(), baseNum.end());
return baseNum;
}
int main()
{
int numOfTestCases = 0;
cin >> numOfTestCases;
unsigned short *Answer = new unsigned short[numOfTestCases];
unsigned short ansIndx = 0;
const unsigned int MAX_BASE = 256;
char baseValue[MAX_BASE];
for(int i = 0; i < MAX_BASE; i++){
baseValue = char(i);
}
const BigDataType MAX = 10e10;
while(numOfTestCases--)
{
BigDataType num;
cin >> num;
if(num < 1 || num > MAX)
continue;
for(unsigned int base = 2; base < MAX_BASE; ++base)
{
if(isPalindrome( getBase( num, base, baseValue ) ) ){
Answer[ansIndx++] = base;
break;
}
}
}
for(int i = 0;i < ansIndx; i++){
cout << Answer << endl;
}
delete [] Answer;
return 0;
}
Frustrating problem.
So I am just practicing on my logic by trying to solve some code chef problems.
The particular problem is this problem .
I believe my solution should work, but however, it keeps telling me that its
wrong. Maybe there is a special case or something that I forgot to cover. Any
help should be greatly appreciated, because its really, really, and I mean really, frustrating me.
Here is my attempt. I didn't comment because I think it should be straight
forward.
Feel like a noob.
The site was telling me that my answer was wrong. But as far as I can see,
it should work. I thought there might be a special case that I haven't covered
that someone might see.
it should work. I thought there might be a special case that I haven't covered
that someone might see.
You are only checking bases up to 255. Did you try checking to see if there are any numbers that go over that?
Also, if you're only checking for palindromes, there's no need to reverse the string before checking it. (Not that this affects the correctness of the code.)
Also, if you're only checking for palindromes, there's no need to reverse the string before checking it. (Not that this affects the correctness of the code.)
You could use a vector of ints.
Here's a modification of your code. I didn't test it, but it should give you the right idea.
Here's a modification of your code. I didn't test it, but it should give you the right idea.
typedef unsigned long Uint32;bool IsPalindromeInBase(BigDataType num, Uint32 base){ std::vector<Uint32> thestring; while(num > 0) { thestring.push_back(num % toBase); num /= toBase; } for( Uint32 i =0; i < (thestring.size() - i); ++i) { if ( thestring.at(i) != thestring.at(thestring.size() - i) ) { return false; } } return true;}
How about instead of storing your numbers as char's, you store them in a more general fashion, such as with your BigDataType type. Instead of using a string then, just use a vector of BigDataType's.
*edit*
Arg, ninja'd
*edit*
Arg, ninja'd
so you are suggesting that I should store a vector of ints instead of an array
of chars, and work with them the same way as I did with the chars?
What if the num % base return a 2 digits of greater number, then how will that
work?
of chars, and work with them the same way as I did with the chars?
What if the num % base return a 2 digits of greater number, then how will that
work?
So I think I got it working, but obviously stepping through each base is not
efficient. Anyone want to hint me on some theory about bases?
efficient. Anyone want to hint me on some theory about bases?
A quick search of Wikipedia didn't turn up anything particularly interesting, although it did confirm that some numbers do require bases larger then 255 to be palindromic. For example, 263 is not palindromic in any base below 262.
I doubt that there is any particular algorithm for this. Anyway, with small numbers like 10^10, it should be instantaneous on any modern processor.
It's only once you start using bignums that it becomes slow.
I doubt that there is any particular algorithm for this. Anyway, with small numbers like 10^10, it should be instantaneous on any modern processor.
It's only once you start using bignums that it becomes slow.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement