nhreddy@uci.edu
BAN USERGuys. This is not a correct solution. I will correct it and post it in a few days. Please look below.
- nhreddy@uci.edu October 06, 2014This question is a bit tricky. This is the logic I propose.
Put the numbers in an array A[n] (referenced by 0 to n-1)
For k=1:
Swap A[k-1] with the maximum number in A[k : n-1] such that the number is greater than A[k-1]. If there are 2 such numbers of same value greater than A[k-1], pick the rightmost one(one with larger index).
.
.
.
For k=i:
Swap A[k-i] with the maximum number in A[k : n-1] such that the number is greater than A[k-i]. If there are 2 such numbers of same value greater than A[k-i], pick the rightmost one(one with larger index).
Basic Selection Sort logic with a little modification till K-steps.
Whatever remains in the array is the solution.
Time : O(n) * k = effectively O(n)
This is not as complex as you think. It is not the problem of adding characters to make a string a palindrome. It is much simpler. It is just adding characters only to the beginning of the string. Insertions are only in the beginning,
You just need to compare the last character to the first character. If these two are the same then you check if the rest of the string is a palindrome. If it is then no additions required.
Otherwise you add one to the count and check for the last but one character and so on.
Here is a recursive solution:
This is an O(n) solution.
- nhreddy@uci.edu November 27, 2014The output is:
The result number of aaacecaaa is : 9
The result number of acecaaa is : 9
The result number of racexyzart is : 19