Odd To Even

Easy
0/40
Average time to solve is 10m
profile
Contributed by
55 upvotes
Asked in companies
Morgan StanleyQualcommLTIMindtree

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
652345
79345
31179
Sample Output 1:
655342
79354
-1
Explanation For Sample Input 1:
In test case 1: 

552346, 655342, 652354 are the all possible even number which can be made by only using 1 swap operation.

Out of which 655342 is the largest, hence the answer.

In test case 2:
The only possible even number is 79354.

In test case 3:
There is no possible way to swap two digits to make the number even.
Sample Input 2:
2
635875915
64966689669
Sample Output 2:
635575918
94966689666
Hint

Generate all possible even numbers then print the largest out of them

Approaches (2)
Brute force
  • 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.
Time Complexity

O(N ^ 2),  where N is the length of the string

 

There can be ‘N - 1’ strings of length N in the vector in the worst case.

 

The worst-case being ee….eo  i.e. only one odd number at one’s place.

Space Complexity

O(N ^ 2),  where N is the length of the string

 

There can be ‘N - 1’ strings of length n in the vector in the worst case.

Code Solution
(100% EXP penalty)
Odd To Even
Full screen
Console