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.
I've got it after looking at a few test cases and checking the logic of my approach.
Here is some info:
Since you are given a limit number of digit replacements (k) and you want the resulted palindrome number maximized, you need to first learn the minimum number of replacement needed (minReplacementNeeded) to fix the given number so that it becomes a palindrome number. You then derive the number of extra replacements (extraReplacements). The number is biggest when you replace any non-9-digit from the left to digit 9 based on the number of extra replacements, etc. (extraReplacements).
Basically:
1. Scan the string character by character once to obtain minReplacementNeeded
2. extraReplacements = k - minReplacementNeeded
3. Scan the string character by character (until minReplacementNeeded and extraReplacements are used up or we reach the end of the string) to do the character replacement operation based on extraReplacement and minReplacementNeeded
This is O(N) time where N is the number of characters in the given string.
Here is my explanation based on the test that "abzalovim" mentions:
Given:
8 4
11119111
Expected output: 91199119
Why?
s="11119111"
k = 4
n = 8
1. minReplacementNeeded = 1
s[3] = '1' vs. s[4] = '9'
You use 2 out of three extra replacements that are not needed to make the resulting number as big as possible.
Explicitely, s[0] and s[7], set them to '9' (two replacements)
There is one extra replacement left but you can't use it as there is an even number of digits (n % 2 = 0) and for this particular case, you need an even number of extra replacements.
One needed replacement is for setting s[3] to '9'
The result string is, therefore, "91199119" with only 3 replacements used.
Further, if given
8 4
11919111
Then the resulted string is "91999919" with all four replacements used.
** Here are five more test cases which are variant of the above test case:
TC-01:
Given
8 2
11119111
=> Expected result: 11199111 with one replacement
(same result if give k = 1)
TC-02:
Given
7 1
1111111
=> Expected result: 1119111
TC-03:
Given
7 4
1111111
=> Expected result: 9911199 with 4 replacements (one replacement operation left which cannot be used)
TC-04:
Given
7 4
1191111
=> Expected result: 9199919 with 4 replacements (one replacement operation left which cannot be used)
Highest Value Palindrome
You are viewing a single comment's thread. Return to all comments →
I've got it after looking at a few test cases and checking the logic of my approach.
Here is some info: Since you are given a limit number of digit replacements (k) and you want the resulted palindrome number maximized, you need to first learn the minimum number of replacement needed (minReplacementNeeded) to fix the given number so that it becomes a palindrome number. You then derive the number of extra replacements (extraReplacements). The number is biggest when you replace any non-9-digit from the left to digit 9 based on the number of extra replacements, etc. (extraReplacements).
Basically: 1. Scan the string character by character once to obtain minReplacementNeeded 2. extraReplacements = k - minReplacementNeeded 3. Scan the string character by character (until minReplacementNeeded and extraReplacements are used up or we reach the end of the string) to do the character replacement operation based on extraReplacement and minReplacementNeeded
This is O(N) time where N is the number of characters in the given string.
Here is my explanation based on the test that "abzalovim" mentions: Given: 8 4 11119111
Expected output: 91199119
Why? s="11119111" k = 4 n = 8 1. minReplacementNeeded = 1 s[3] = '1' vs. s[4] = '9'
extraReplacements = k - minReplacementNeeded = 4 - 1 = 3
You use 2 out of three extra replacements that are not needed to make the resulting number as big as possible. Explicitely, s[0] and s[7], set them to '9' (two replacements) There is one extra replacement left but you can't use it as there is an even number of digits (n % 2 = 0) and for this particular case, you need an even number of extra replacements.
One needed replacement is for setting s[3] to '9' The result string is, therefore, "91199119" with only 3 replacements used.
Further, if given 8 4 11919111 Then the resulted string is "91999919" with all four replacements used.
** Here are five more test cases which are variant of the above test case:
=> Expected result: 11199111 with one replacement (same result if give k = 1)
Hope it helps. Thanks.