New update is available. Click here to update.

Odd To Even

PROBLEM STATEMENT

You are given an odd number in the form of a string, ‘S.’ Your goal is to convert the number into an even number such that the following two conditions are satisfied.

You can use swap operation over any two indices i,e you can choose two indices 'i' and 'j' and swap the digits present at S[i] and S[j]. But this operation can be used only once.

Your final even number should be the largest out of all other possible even numbers.

Note:

If it isn’t possible to make an even number print -1

Input Format:

The first line of the input contains ‘T’ denoting the number of test cases.

The first and the only line of each test case contains a string ‘S’ the odd number.

Output Format:

If it is possible to make even number print largest out of all. Else print -1

Print the result of each test case in a new line.

Constraints:

1 <= T <= 5
0 <= |S| <= 10^5

Time Limit : 1 sec

Approach 1

Since we need to convert odd numbers to even numbers, we need to first check if it is possible to do it or not, which can be done by finding even digits in the number.
After which if even digits exist, we need to swap all the positions with even digits with the last digit (at one’s place) to make it even and store this new string in an array of strings.
After storing all possible strings, we find and return the largest of them.

Algorithm:

If there is no even digit in the number, return -1.
Iterate over the number (string) and find positions which have even digit, then swap this position to last position (at one’s place). Store this new string in a vector.
Return the largest string in the vector.

Try Problem

Approach 2

If the number is x8xx4xx6xxx7, then it is optimal to swap 4 with 7 to make it even. Why??

It is because when replacing the odd digit with an even digit it is always optimal to replace it with a digit that is smaller or equal to it, this is done so that the final number doesn’t end up smaller than the original.
And out of all the even digits smaller than an odd digit, we pick the leftmost because it is a more significant digit. If there is no even digit smaller than the odd digit, we replace it with the least significant (rightmost) digit.

Algorithm:

If there is no even digit in the number, return -1.
Initialize last as -1, which keeps the last index with an even digit.
Iterate over the number (string) and find positions which have an even digit, if the digit is smaller than a digit at one’s place then swap it and return it, if not then update the last variable with the current index.
After the end of the iteration, swap the odd digit at one’s place with the last variable. And return the string.

Try Problem