Palindromic Representations in Different Bases
National Olympiad — National round (2012 season)
Submission name: number.cpp
Problem summary
Find every base from 2 through 36 in which n has a palindromic ordinary representation.
Input
One decimal integer n.
Output
none, or unique/multiple followed by all qualifying bases on a second line.
Constraints
1 ≤ n ≤ 10^9; bases 2…36 inclusive.
Worked example
Input and output for the worked example discussed below.
Input
123
Output
unique 6
Solution analysis
- Convert n to each candidate base by repeatedly recording the remainder and dividing by the base. The stored list is reversed, but reversal does not change whether it is a palindrome.
- Compare opposite numeric digit values. Bases above 10 need no letter mapping because equality of digit values suffices. Record accepted bases in increasing iteration order.
- For 123, base 6 gives digits [3,2,3], representing 323₆. It is the only accepted base, so print unique and 6. Any one-digit representation is automatically palindromic.
Why it works
Repeated division recovers the exact digits. Opposite-position equality is precisely the palindrome condition, and every permitted base is checked once. The accepted-list size determines the required first-line classification.
Watch out. Compare digit values, not decimal spellings of individual digits. Include single-digit representations and print no second line after none.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int number;
cin>>number;
vector<int>answers;
for(int base=2;base<=36;base++){
int value=number;
vector<int>digits;
do{
digits.push_back(value%base);
value/=base;
}
while(value>0);
bool valid=true;
// Numeric digit equality also handles bases above ten.
for(int i=0;i<int(digits.size())/2;i++){
if(digits[i]!=digits[digits.size()-i-1]){
valid=false;
}
}
if(valid){
answers.push_back(base);
}
}
if(answers.empty()){
cout<<"none\n";
return 0;
}
cout<<(answers.size()==1?"unique":"multiple")<<'\n';
for(size_t i=0;i<answers.size();i++){
if(i>0){
cout<<' ';
}
cout<<answers[i];
}
cout<<'\n';
}