HackerRank Highest Value Palindrome Solution
In this post, we will solve HackerRank Highest Value Palindrome Solution.
Palindromes are strings that read the same from the left or right, for example madam or 0110.
You will be given a string representation of a number and a maximum number of changes you can make. Alter the string, one digit at a time, to create the string representation of the largest number possible given the limit to the number of changes. The length of the string may not be altered, so you must consider O’s left of all higher digits in your tests. For example 0110 is valid, 0011 is not.
Given a string representing the starting number, and a maximum number of changes allowed, create the largest palindromic string of digits possible or the string ‘-1’ if it is not possible to create a palindrome under the contstraints.
Example
s = ‘1231’
k = 3
Make 3 replacements to get ‘9339’.
8 = ‘12321’
k = 1
Make 1 replacement to get ‘12921’.
Function Description
Complete the highestValuePalindrome function in the editor below.
highestValuePalindrome has the following parameter(s):
- string s: a string representation of an integer
- int n: the length of the integer string
- int k: the maximum number of changes allowed
Returns
- string: a string representation of the highest value achievable or
-1
Input Format
The first line contains two space-separated integers, n and k, the number of digits in the number and the maximum number of changes allowed.
The second line contains an n-digit string of numbers.
Output Format
Sample Input 0
STDIN Function
----- --------
4 1 n = 4, k = 1
3943 s = '3943'
Sample Output 0
3993
Sample Input 1
6 3
092282
Sample Output 1
992299
Sample Input 2
4 1
0011
Sample Output 2
-1Explanation
Sample 0
There are two ways to make 3943 a palindrome by changing no more than k = 1 digits:
1.3943 3443
2.39433993
3993 > 3443
Highest Value Palindrome C Solution
// https://www.hackerrank.com/challenges/richie-rich
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
int changesNeededF(char *number, int n) {
int changes = 0;
for(int i = 0; i < (n / 2); i++) {
if(number[i] != number[n - 1 - i]) {
changes++;
}
}
return changes;
}
int doubleChange(char *number, int n, int k) {
int changes = 0;
for(int i = 0; i < (n / 2) && k; i++) {
if ((number[i] != '9') && (number[n - 1 - i] != '9')) {
if(number[i] == number[n - 1 - i]) {
if(k < 2) {
continue;
} else {
k--;
}
}
number[i] = '9';
number[n - 1 - i] = '9';
changes += 2;
k--;
}
}
return changes;
}
int palindromize(char *number, int n) {
int changes = 0;
for(int i = 0; i < (n / 2); i++) {
if(number[i] != number[n - 1 - i]) {
number[i] = MAX(number[i], number[n - 1 - i]);
number[n - 1 - i] = MAX(number[i], number[n - 1 - i]);
changes++;
}
}
return changes;
}
int maximize(char *number, int n, int k) {
int changes = 0;
for(int i = 0; i < (n / 2) && k > 1; i++) {
if(number[i] != '9') {
number[i] = '9';
number[n - 1 - i] = '9';
changes += 2;
k -= 2;
}
}
if(n%2 && k) {
number[n/2] = '9';
}
return changes;
}
int main(){
int n;
int k;
scanf("%d %d",&n,&k);
char* number = (char *)malloc(102400 * sizeof(char));
scanf("%s",number);
int changes;
int changesNeeded = changesNeededF(number, n);
if(changesNeeded > k) {
printf("-1\n");
} else {
changes = doubleChange(number, n, k - changesNeeded);
k -= changes;
changes = palindromize(number, n);
k -= changes;
maximize(number, n, k);
printf("%s\n", number);
}
return 0;
}Highest Value Palindrome C++ Solution
#include <bits/stdc++.h>
using namespace std;
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
const int MOD = 1000000007;
template<class T> inline T tmin(T a, T b) { return (a < b) ? a : b; }
template<class T> inline T tmax(T a, T b) { return (a > b) ? a : b; }
template<class T> inline void amax(T &a, T b) { if (b > a) a = b; }
template<class T> inline void amin(T &a, T b) { if (b < a) a = b; }
template<class T> inline T tabs(T a) { return (a > 0) ? a : -a; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }
int main(int argc, char *argv[]) {
ios_base::sync_with_stdio(false);
int n, k;
string s;
cin >> n >> k >> s;
int hn = n >> 1;
int diff = 0;
REPU(i, 0, hn) {
if (s[i] != s[n - 1 - i]) diff++;
}
if (diff > k) {
puts("-1"); return 0;
}
int rem = k;
REPU(i, 0, hn + 1) {
if (rem <= 0) break;
if (s[i] != s[n - 1 - i]) {
diff--;
if (s[i] == '9' || s[n - 1 - i] == '9') {
s[i] = s[n - 1 - i] = '9';
rem--;
}
else if (rem - 2 >= diff) {
s[i] = s[n - 1 - i] = '9';
rem -= 2;
}
else {
if (s[i] > s[n - 1 - i]) s[n - 1 - i] = s[i];
else s[i] = s[n - 1 - i];
rem--;
}
}
else if (i != n - i - 1 && s[i] < '9' && rem - 2 >= diff) {
s[i] = s[n - 1 - i] = '9';
rem -= 2;
}
else if (i == n - i - 1 && s[i] < '9' && rem - 1 >= diff) {
s[i] = '9';
rem--;
}
}
printf("%s\n", s.c_str());
return 0;
}Highest Value Palindrome C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
static void Main(String[] args) {
string[] tmp = Console.ReadLine().Split(' ');
int n = int.Parse(tmp[0]), k = int.Parse(tmp[1]);
string left = Console.ReadLine();
if (n == 1) {
if (k > 0) left = "9";
Console.WriteLine(left);
return;
}
string right = new string(left.Reverse().ToArray()).Substring(0, n / 2);
string middle = "";
if (n % 2 == 1) { middle = left[n / 2].ToString(); }
left = left.Substring(0, n / 2);
var changedl = new List<int>();
var changedr = new List<int>();
StringBuilder sl = new StringBuilder(left);
StringBuilder sr = new StringBuilder(right);
left = null; right = null;
int i = 0;
while (i < n / 2 && k> 0) {
if (sl[i] != sr[i]){
k--;
if (sl[i] > sr[i]) {
sr[i] = sl[i];
changedr.Add(i);
} else {
sl[i] = sr[i];
changedl.Add(i);
}
}
i++;
}
if (!sl.Equals(sr)) { Console.WriteLine(-1); } else {
i = 0;
while (i < n / 2 && k > 0) {
if (int.Parse(sl[i].ToString()) < 9) {
if (changedr.Contains(i) || changedl.Contains(i)) k++;
if (k >= 2) {
sl[i] = '9';
sr[i] = '9';
k -= 2;
}
}
i++;
}
if (middle != "" && middle != "9" && k > 0) middle = "9";
Console.WriteLine(sl.ToString() + middle + new string(sr.ToString().Reverse().ToArray()));
}
}
}Highest Value Palindrome Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'highestValuePalindrome' function below.
*
* The function is expected to return a STRING.
* The function accepts following parameters:
* 1. STRING s
* 2. INTEGER n
* 3. INTEGER k
*/
public static String listToString(List<Integer> characters)
{
return characters.stream().map(i->(char)(i+48)).map(String::valueOf).collect(Collectors.joining());
}
public static int countRequiredChanges(List<Integer> intValues)
{
int count = 0;
for (int i = 0; i<intValues.size()/2; ++i)
{
if (!Objects.equals(intValues.get(i), intValues.get(intValues.size() - i - 1)))
count++;
}
return count;
}
public static String highestValuePalindrome(String s, int n, int k) {
// Write your code here
List<Integer> intValues = s.chars().boxed().map(i -> i - 48).collect(toList());
int required = countRequiredChanges(intValues);
if (required > k)
return "-1";
for (int i = 0; i<intValues.size()/2; ++i)
{
int fstIndex = i;
int sndIndex = intValues.size()-i-1;
if (Objects.equals(intValues.get(i), intValues.get(sndIndex)))
{
if (k-2>=required && intValues.get(i) != 9)
{
intValues.set(i, 9);
intValues.set(sndIndex, 9);
k-=2;
}
continue;
}
Integer maxValue = Math.max(intValues.get(i), intValues.get(sndIndex));
if (maxValue == 9)
{
intValues.set(i, maxValue);
intValues.set(sndIndex, maxValue);
k--;
required--;
continue;
}
if (k>required)
{
maxValue = 9;
k--;
}
intValues.set(i, maxValue);
intValues.set(sndIndex, maxValue);
k--;
required--;
}
if (k > 0 && s.length() % 2 == 1)
intValues.set(s.length()/2, 9);
return listToString(intValues);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int k = Integer.parseInt(firstMultipleInput[1]);
String s = bufferedReader.readLine();
String result = Result.highestValuePalindrome(s, n, k);
bufferedWriter.write(result);
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}Highest Value Palindrome JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
function main() {
var n_temp = readLine().split(' ');
var n = parseInt(n_temp[0]);
var k = parseInt(n_temp[1]);
var number = readLine();
var arr = number.split('');
var i, lo, hi, modCount, modified = [];
for (i = 0; i < n; i++) {
arr[i] = parseInt(arr[i], 10);
}
if (k >= n){
for (i = 0; i < n; i++){
arr[i] = 9;
}
} else {
for (i = 0; i < n/2; i++){
modified[i] = false;
}
modCount = 0;
lo = 0;
hi = n-1;
while (lo < hi && modCount < k){
if (arr[lo] !== arr[hi]){
if (arr[lo] > arr[hi]){
arr[hi] = arr[lo];
} else {
arr[lo] = arr[hi];
}
modified[lo] = true;
modCount += 1;
}
lo += 1;
hi -= 1;
}
// check that we have a palindrome
while (lo < hi){
if (arr[lo] !== arr[hi]){
console.log(-1);
return;
}
lo += 1;
hi -= 1;
}
// if we have modifications left, make numbers as big as possible
lo = 0;
hi = n-1;
// here we handle the case when lo = hi for when we have an odd number of digits
while (modCount < k && lo <= hi){
if (arr[lo] !== 9){
if (modified[lo] || lo === hi){
arr[lo] = 9;
arr[hi] = 9;
modCount += 1;
} else if (modCount + 2 <= k){
arr[lo] = 9;
arr[hi] = 9;
modCount += 2;
}
}
lo += 1;
hi -= 1;
}
}
console.log(arr.join(''));
}Highest Value Palindrome Python Solution
[numDigits, numChanges] = [int(a) for a in input().split()]
number = input()
def numberOfChangesNeeded(number):
l = list(number)
needed = 0
for i in range(int(len(l) / 2)):
if l[i] != l[-(i + 1)]:
needed += 1
return needed
numChangesNeeded = numberOfChangesNeeded(number)
if numChangesNeeded > numChanges:
print(-1)
elif numChanges > len(number):
print('9' * len(number))
else:
number = list(number)
i = 0
changesMade = 0
changes = [0] * len(number)
while(changesMade < numChanges and i < int(len(number) / 2)):
a = number[i]
b = number[-(i+1)]
if int(a) < int(b):
number[i] = b
changes[i] = 1
changesMade += 1
elif int(a) > int(b):
number[-(i+1)] = a
changes[-(i+1)] = 1
changesMade += 1
i += 1
changesLeft = numChanges - changesMade
i = 0
while (changesLeft > 0 and i < int(len(number) / 2)):
if number[i] != '9' and number[-(i+1)] != '9' and (changesLeft + changes[i] + changes[-(i+1)] > 1):
number[i] = '9'
if not changes[i]:
changes[i] = 1
changesLeft -= 1
number[-(i+1)] = '9'
if not changes[-(i+1)]:
changes[-(i+1)] = 1
changesLeft -= 1
i += 1
if changesLeft == 1 and len(number) % 2 == 1:
number[int(len(number) / 2)] = '9'
print(''.join(number))
Other Solutions
