Jump to content
  • Advertisement
Sign in to follow this  
Concentrate

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.

If you intended to correct an error in the post then please contact us.

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 ) ) ){
				Answer[ansIndx++] = base;
				break;
			}					
		}
	}
 
	for(int i = 0;i < ansIndx; i++){
		cout << Answer << endl;
	}

	delete [] Answer;

	return 0; 
}


Feel like a noob.

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!