CGNPAL-editorial

general
1

PROBLEM LINK

click here for problem

Setter- pavan sai kiran

Editorial - pavan sai kiran

DIFFICULTY:

Easy

PREREQUISITES

Palindrome,radix number system

PROBLEM

You will be given a number ‘n’ and a radix base ‘b’ and now you have to convert that number into its corresponding in the base ‘b’ and check whether it is a palindrome or not.

Explanation

what you have to do is just run a while loop and keep on dividing the given number ‘n’ with base ‘b’
till the number ‘n’ becomes 0 and store all the remainders in an array.

Now if we combine the numbers in that array from right to left and form a new number , now this number is the actual number that ‘n’ in radix base ‘b’.

Now you just have to check whether this number is a palindrome or not and for this you just need to check whether ith element in the array is equal to l-i-1th element in the array where l is the length of the array for all i=0,1,2,3…,l/2.

for example n=16 and b=3 now the array will be [1,2,1]

here l=3 and i=0,1

the statement ith element in the array is equal to l-i-1th element is satisfied.

Therefore, this is a palindrome and thus “YES” must be printed.

Solution

Setter’s solution can be found here.

2

Since “most numbers” are not palindromes in a given base, I took the alternative approach of checking from both ends.

First find the highest power of b that is less than or equal to n, then chop off the top and bottom digits and compare them. If they match, repeat (dividing the high power by b^2 each time) until the remaining portion is below b or a non-match is found. If you reach a remaining digit below b after a full set of match digits, this is the central digit (or if zero there may be no central digit) which doesn’t affect the “palindromicity”.

Compared to the editorial solution:
Disadvantage: more calculation for palindromes
Advantage: early completion for many non-palindromes, check as you go
Could be either: no storage of full base representation

Solution here

3

You might like to add a test case somewhere with n = b. My first submission sneaked through with a bug that would have failed on that.