Hackerank palindrome problem

[rozick1]

Hi all

I'm doing the Richie Rich hackerrank problem. Link is here: https://www.hackerrank.com/challenges/richie-rich but in essence you have to make a number the largest possible palindrome given the possibility of making up to k changes (counting as a change in one digit).

I'm not looking for someone to solve this for me but just let me know if I'm on the right lines. I've pasted below some very basic code but more importantly some comments as to how to approach the problem.

Many thanks

#include <iostream>

using namespace std;

int main()
{
   string str = "092282";
   int k = 3;
   
   int minChanges = 0;
   
   for (int l=0, r = str.size()-1; l < str.size() /2;l++,r--) //minimum number of changes required?
       if (str[l] != str[r])
            minChanges++;
       
   if (minChanges <= k) // palindrome possible 
   {
       //options
         //if l and r are different we can either 1(a)change l or r to match the other (to whichever is highest) or 1(b) change both to 9
         //if l and r are the same we can either 2(a) leave as is or 2(b) change both to 9
       
       //given we want str to be the largest number we should (where possible) use option 1/2(b) with priority to lefthandside
       
       //option 1(a) costs 1 k whilst 1/2(b) costs 2 k 
       //given minChanges and k, which options do we take?
        //if minChanges == k then we can only take option 1(a)
        //if minChanges < k then we can use spare Ks for option 1/2(b) with lefthand priority
   }
   
   else
   {
       cout << "-1\n";
   }
   
   return 0;
}

[dhayden]

Yes, I think you're on the right track. Furthermore, I applaud you for sketching out the algorithm with comments. One note though: you'll have to update minChanges and k as you make the second pass through the string.

I suspect that you'll find the algorithm easier to express if you consider minChanges vs. k first, and then decide what to do with it. Maybe something like:

if (minChanges == k) {
    // if digits are different then change smaller to match larger
} else if (minChanges >= k+2) {
   // You have spare changes. Change one or both (or neither!) to '9'
} else (minChanges == k+1) {
   // You can make one extra change.  If the digits are different, then change the smaller
   // to match the larger.
}

[rozick1]

Thanks

There are lots of horrible corner cases which I'm eliminating one by one!

[dhayden]

It's definitely a deceptively complex problem. The good news is that the examples on the website seem to hit many of the corner cases. Please post your code when you're done. It's definitely a cool problem.

Good luck!