# Frustrating problem.

## 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[i] = 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.

##### Share on other sites
I need a second opinion. Can you check if there is something I can do better?

Here is what I have so far :
#include <iostream>#include <string>#include <deque>using namespace std;typedef long long BigDataType;#define DEBUG	1#if (DEBUG )	#include<ctime > // for time#endifbool isPalindromeInBase(BigDataType num, const unsigned int& newBase){	std::deque<unsigned int> baseNum;				float inverseBase = 1.0f/newBase;	while(num > 0){		baseNum.push_back(num % newBase);				num *= inverseBase;	}	int begin = 0;	int end = baseNum.size() - 1;	while(begin < end){		if( baseNum[begin++] != baseNum[end--] ) 			return false;	}	return true;}int main(){								int numOfTestCases = 0;	if(DEBUG)		numOfTestCases = 10;    else     	scanf("%d", &numOfTestCases );	unsigned short Answer[1100];	unsigned short ansIndx = 0;	const BigDataType MAX = 10e10;	unsigned long base = 2;	while(numOfTestCases--)	{		BigDataType num;		if( DEBUG )			num = rand()*(MAX - 1) + 1;		else			scanf("%lld", &num );		while(!isPalindromeInBase(num,base) ){			base++;		}		Answer[ansIndx++] = base;				if( DEBUG ){			cout <<num << " is palindrome at base : " << Answer[ansIndx  - 1] << endl;		}		base = 2; //reset	} 	if(! DEBUG )		for(int i = 0; i < ansIndx; i++){			printf("%lu\n", Answer[i]);		}			return 0; }

I was using scanf and printf for faster speed. Plus, I never used the #define DEBUG method before, hope I am using it correctly.

##### Share on other sites
In this code :

while(num > 0){   baseNum.push_back(num % newBase);		   num *= inverseBase;}

You think we can check( if palindrome) while converting( to radix r )?

##### Share on other sites
This can be solved without external storage (queue, vector, etc...).

Given number N in base B, how many digits are needed to represent it (it has to do with logarithms)? How does this help you determine what the individual digits are?

What is palindrome? Consider B=10 and N=2112

There are 4 digits, so multipliers will be 1, 10, 100 and 1000. To test for palindrome, test
- (2)112 (digit 4, mutliplier 1000) == 211(2) (digit 1, multiplier 1
and
- 2(1)12 (digit 3, multiplier 100) == 21(1)2 (digit 2, multiplier 10).

Same thing for other bases.

Think about how you would implement this generically. You need a way to find out how many digits are needed to represent number N in base B, and how to calculate any given digit in base B.

##### Share on other sites
I think a puzzle of these types of sites are meant to be solved by the person, who tries to solve it, so what's the point of having it solved by others? Where's the fun? Or is it for money? Then where's the helpers' percentage?

Shit, I just cannot make the first sentence to make sense.

##### Share on other sites
>>This can be solved without external storage (queue, vector, etc...).

Through some trial, I find that the number of digits needed to represent a number
from base A, to number in base B is calculate by :
int maxDigNeeded = ceil(log( double(num) ) / log ( double(newBase) ));

>>Given number N in base B, how many digits are needed to represent it (it has to do with logarithms)? How does this help you determine what the individual digits are?

What is palindrome? Consider B=10 and N=2112

There are 4 digits, so multipliers will be 1, 10, 100 and 1000. To test for palindrome, test
- (2)112 (digit 4, mutliplier 1000) == 211(2) (digit 1, multiplier 1
and
- 2(1)12 (digit 3, multiplier 100) == 21(1)2 (digit 2, multiplier 10).

Same thing for other bases.

Think about how you would implement this generically. You need a way to find out how many digits are needed to represent number N in base B, and how to calculate
any given digit in base B.

I see what you did. But how I am not sure this palindrome checker will help
enough.

>>I think the problems of these types of sites are meant to be solved by the person, who tries to solve it, so what's the point of having it solved by others? Where's the fun? Or is it for money? Then where's the helpers' percentage?

True,but I asked for helpful hints, and some theories that I may not know of
for this particular subject. I did not ask for the blatant solution. In fact
they show the solution of other already, so if I just wanted the points from
them, I would just hand in their solution. Its not for money. There is no
helpers' percentage.

##### Share on other sites
Quote:
 Original post by ConcentrateIn this code : while(num > 0){ baseNum.push_back(num % newBase); num *= inverseBase;}You think we can check( if palindrome) while converting( to radix r )?

Why on earth are you storing the reciprocal of the base as a floating point and multiplying by that?

With floating points, you'll get rounding errors and loss of significance. It will make your program give incorrect results!
Plus it doesn't actually make it any faster. In fact, switching to floating points probably makes it slightly slower.

##### Share on other sites
Thanks. Do you think this brute force can be improved :
while(!(isPalindromeInBase(num,base)) ){	base++;}

Checking from base 2 to base n, is really not good. I am trying some stuff,
but can't think of anything.

##### Share on other sites
Quote:
 Original post by ConcentrateI see what you did. But how I am not sure this palindrome checker will helpenough.

This is not a hard problem per-se, it's more about exploring different ways of implementing same algorithm.

Here is a solution without storage.
#include <cmath>#include <cstdio>typedef int num_t;// test pairs of digits for equality// 5115, test outer 5 and 5, then inner 1 and 1void test(num_t val) {	// check bases from 2 to val-1 inclusively	// val is biggest base in which val can be represented	for (num_t base = 2; base < val; base++) {		// right cursor is always right-most digit		num_t right = 1;		// left cursor is left-most digit		num_t left = (num_t)pow((double)base, floor(log((double)val) / log((double)base)));		// check if current left and right digits are same		while ((val / left) % base == (val / right) % base) {			// move cursors inward			left /= base;			right *= base;			if (left <= right) {				// if cursors met, all pairs were equal, it's a palindrome				// if cursors point to same digit, number of digits is odd (919), and it's a palindrome				printf("%d\n", base);				return;			}		}		// not a palindrome, try next base	}}int main (){	num_t val;	while (scanf("%ld", &val) == 1) test(val);}
Comments make it look larger than it really is.

The basic idea is:
- convert number into specific base (implicitly done in calculations)
- set cursors to left and right most digit
- while digits at cursors are equal
-- move cursors inward
-- if cursors meet, it's a palindrome

There might be other rules that could be exploited, for example, if a number in some base is not palindrome, then it cannot be in other, larger bases either.

Implementing that is annoying though, since one would need some library that deals with large ints. There is some literature on doing base conversions between arbitrary numbers.

##### Share on other sites
Believe or not, my algo before this was similar to that( maybe not as good), but
it still ran over the time limit. There is about 1000 test cases of number ranging from 1 to 10^10 so I am guessing that its the checking from base 2 to base n, is
where they expect us to improve, I think.

Do you think, certain types of numbers, like primes and so might have a higher
palindromic base?

##### Share on other sites
I just registered at CodeChef for fun and got 1.69 seconds.

Here's a hint. Think about what possible values the base can be in order for n to be a palindrome.

##### Share on other sites
Quote:
 Original post by StoryyellerI just registered at CodeChef for fun and got 1.69 seconds.Here's a hint. Think about what possible values the base can be in order for n to be a palindrome.

Thanks for rubbing it in, lol.

##### Share on other sites
lol this site is awesome. :D

##### Share on other sites
>>Here's a hint. Think about what possible values the base can be in order for n to be a palindrome.

Is this true :

Let testNumber = random( 1 , 10e10 );

Then if sqrt( testNumber ) does not have the smallest base, then 2*sqrt(test)
number also does not the smallest base?

##### Share on other sites
The algorithm I came up with is based on the observation that if
b>=sqrt(n), then b=n/a - 1 for some integer a.

#include <iostream>#include <vector>typedef unsigned long Uint32;typedef unsigned long long Uint64;const Uint32 MAXVECTORSIZE = 35; //Enough to hold 10^10 in binarystd::vector<Uint32> digits;bool IsPalindromeInBase(Uint64 n, Uint32 base){    digits.clear();    if (n % base == 0) {return false;}    while (n>0)    {        digits.push_back( n % base );        n /= base;    }    for (int i=0; i < (digits.size() - i - 1); ++i)    {        if (digits[i] != digits[digits.size() - i - 1])        {            return false;        }    }    return true;}Uint64 GetSmallestBase (Uint64 n){    Uint32 base;    //Edge cases    if (n==1) {return 2;}    if (n==2) {return 3;}    for (base = 2; ((Uint64) base) * base < n; ++base)    {        if (IsPalindromeInBase(n,base))        {            return base;        }    }    --base;    if ( ((Uint64) base) * (base + 1) >= n)    {        --base;    }    for (Uint32 a = base; a>= 2; --a)    {        if (n % a == 0)        {            return n/a - 1;        }    }    return n - 1;}int main(){    int numtests;    digits.reserve(MAXVECTORSIZE);    std::cin >> numtests;    for (int i=0;i<numtests;++i)    {        Uint64 nexttest;        std::cin >> nexttest;        std::cout << GetSmallestBase(nexttest) << '\n';    }}

##### Share on other sites
>>The algorithm I came up with is based on the observation that if
b>=sqrt(n), then b=n/a - 1 for some integer a.

how did you observe that? It doesn't seem like its a common thing to observe.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628344
• Total Posts
2982186

• 9
• 24
• 9
• 9
• 13