Count Binary Palindromes
National Olympiad — National round (2016 season)
Submission name: nbinpal.cpp
Problem summary
Count binary palindromes with exactly n digits, without leading zeroes except that zero itself is a one-digit number.
Input
One integer n.
Output
The number of n-digit binary palindromes.
Constraints
1 ≤ n ≤ 100.
Worked example
Input and output for the worked example discussed below.
Input
5
Output
4
Solution analysis
- A palindrome is determined by its first ceil(n/2) digits: every later digit mirrors an earlier choice. For n>1 the first digit must be 1, leaving ceil(n/2)−1 freely chosen bits.
- Each free bit has two choices, giving 2^(ceil(n/2)−1). For n=1 both 0 and 1 are valid, so return 2 separately.
- For n=5 the free first-half choices are 100,101,110,111; reflecting gives 10001,10101,11011,11111. The largest exponent is 49, safely within long long.
Why it works
Fixing the first half uniquely fixes the mirrored second half, and every permitted first half produces exactly one palindrome.
Complexity: O(1) time and O(1) space: one integer shift after handling n=1.
Watch out. Do not exclude zero when n=1. Use a 64-bit shift operand, not int. For odd length the middle digit is freely chosen once.
Commented C++17 solution
An independently written complete program with standard headers.
// Fixing the first half uniquely fixes the mirrored second half, and every permitted first half produces
// exactly one palindrome..
#include<iostream>
using namespace std;
int main(){
int length;
cin>>length;
if(length==1){
cout<<2<<'\n';
}
else{
cout<<(1LL<<((length+1)/2-1))<<'\n';
}
}