We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This question is all about getting the different cases right. My code passed all test cases. The approach I had is the following. First divide the input into left and right part. If the string length is odd, then you don't care about the middle element just yet. Reverse the right one and find the number of differences between left and right. This difference number would play a key role. Then start looping as many times as the length of left or right string since they have the same length. Each time in the loop, check if number of available changes is greater than or equal the number of differences. This should never be violated because doing so would make it impossible to get a palindrome.
Here are the cases to check.
1- if left[i] == right[i] and the value is not 9
In this case, your goal is to make both numbers 9, but you got to make sure doing so doesn't cause number of change count to get less than number of current difference count.
2- If left[i] != right[i] and either left[i] or right[i] is 9
In this case, you want to make the one which is not 9 as 9. Still you got to make sure doing so doesn't cause number of change count to get less than number of current difference count.
3- if left[i] != right[i] and they are both not 9.
In this case you have 2 ifs.
1- if Available Change Count - 2 >= Different Count -1
in this case you have enough changes in store to change both sides to 9.
2- Else if Available Change Count - 1 >= Different Count -1
In this case you have to determine which is greater in value left[i] or right[i]. Then set the lower value to greater value.
In all above cases, you got to do necassary reduction from Counts. For example if you changed 2 numbers to 9, then you got to subtract 2 from the Available Change Count. You only subtract 1 from the difference count since we only resolved one difference with the 2 changes.
After the loop, my left part has what I need. The answer becomes.
result = left
+
if the length was odd and I have Available Changes left, then make middle element 9, else put middle element as it is
+
reverse(left)
I hope this helps.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Highest Value Palindrome
You are viewing a single comment's thread. Return to all comments →
This question is all about getting the different cases right. My code passed all test cases. The approach I had is the following. First divide the input into left and right part. If the string length is odd, then you don't care about the middle element just yet. Reverse the right one and find the number of differences between left and right. This difference number would play a key role. Then start looping as many times as the length of left or right string since they have the same length. Each time in the loop, check if number of available changes is greater than or equal the number of differences. This should never be violated because doing so would make it impossible to get a palindrome.
Here are the cases to check. 1- if left[i] == right[i] and the value is not 9 In this case, your goal is to make both numbers 9, but you got to make sure doing so doesn't cause number of change count to get less than number of current difference count. 2- If left[i] != right[i] and either left[i] or right[i] is 9 In this case, you want to make the one which is not 9 as 9. Still you got to make sure doing so doesn't cause number of change count to get less than number of current difference count. 3- if left[i] != right[i] and they are both not 9. In this case you have 2 ifs. 1- if Available Change Count - 2 >= Different Count -1 in this case you have enough changes in store to change both sides to 9. 2- Else if Available Change Count - 1 >= Different Count -1 In this case you have to determine which is greater in value left[i] or right[i]. Then set the lower value to greater value.
In all above cases, you got to do necassary reduction from Counts. For example if you changed 2 numbers to 9, then you got to subtract 2 from the Available Change Count. You only subtract 1 from the difference count since we only resolved one difference with the 2 changes.
After the loop, my left part has what I need. The answer becomes.
result = left + if the length was odd and I have Available Changes left, then make middle element 9, else put middle element as it is + reverse(left)
I hope this helps.