Public Group

# Frustrating problem.

This topic is 3196 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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.
#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 ) ) ){
break;
}
}
}

for(int i = 0;i < ansIndx; i++){
}

return 0;
}


Feel like a noob.

##### Share on other sites
What is the question?

##### Share on other sites
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.

##### Share on other sites
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.)

##### Share on other sites
then how will i represent a base thats over 255 ?

##### Share on other sites
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.

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;}

##### Share on other sites
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

##### Share on other sites
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?

##### Share on other sites
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?

##### Share on other sites
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.

1. 1
2. 2
3. 3
4. 4
Rutin
11
5. 5

• 12
• 19
• 10
• 14
• 10
• ### Forum Statistics

• Total Topics
632665
• Total Posts
3007711
• ### Who's Online (See full list)

There are no registered users currently online

×