Minimum number of steps required to make the string even if possible with given operation otherwise return -1

In this article, we are going to learn about a problem in which we are given a number num in the form of a string and tell the minimum number of steps required to make the string even if possible otherwise return -1.

The operation to be performed on the number

• Remove all the digits from the strings that occur more than one time without distorting the order of string num.

• After that, you can Reverse the prefix of length k(in other words, k leftmost digits) of num. So, the leftmost digit is swapped with the k-th digit from the left, the second digit from the left is swapped with (k-1)th left, etc. For example, if num = 386467 and k = 3, then the new value of string num will be 638467.

Note:- k can be equal to the length of the number itself. So, you can reverse the whole number as well.

Example:

Input:

num = 386467

Output:

2

Explanation:

First, we have removed all the digits from the string that occurs more than once So, after removing the digits the new string will be 3847.

After that, we reversed 3847 to 8347 by taking k = 2 and then reverse 8347 to 7438 by taking k = 4. So now the string has been converted to even.

Number of steps required = 2

Efficient Algorithm for the above Problem

Step 1: Initially remove all the digits whose count is more than one without distorting the order of the string digits.

Step 2: If the string become empty after the first operation then return 0.

Step 3: If the string is not empty then check whether the given number is itself an even or not.

Step 4: If num is itself even then return 0 steps are required.

Step 5: If not then check from the leftmost digit of a number where the first even comes as the first even encounters reverse the first k prefix.

• If the first digit from the left is even then take k = length of the number and reverse the whole number and the number will become even in 1 operation only.

• If the first digit is not even then traverse from left most digits of a number and as the even digits encounter reverse the first k prefix and after reversing the first k prefix you will have the first digit as even and now you have got the condition as the previous step. So a maximum of 2 steps will be required if possible.

• If on traversing you did not get any even digit up to the end -1 digits of the number then return -1 because not possible to make the number even.

Let's see the implementation for the above approach as given below: -

#include<bits/stdc++.h>
using namespace std;

int getDigit(string &n){
    // storing the steps required or not
    int status;
    status = -1;
      // making the copy of orginal string into the temp
    string temp = n;

      // storing the count of the every digit char into
      // the count
    map<char, int> count;
    for(int i = 0; i < temp.size(); i++){
        count[temp[i]]++;
    }
      // storing the duplicate character
    set<char> duplicate;
    for(auto value: count){
        if(value.second > 1){
            duplicate.insert(value.first);
        }
    }
      // updating the original string
    n = "";
    for(int i = 0; i < temp.size(); i++){
        if(duplicate.find(temp[i]) == duplicate.end()){
            n.push_back(temp[i]);
        }
    }
    // checking if the first number is even or not
    // if even steps will be 1 
    if((n[0]-48)%2 == 0){
        status = 1;
    }
    else{
        // checking here is there any even digits 
        // is present in the number
        for(int i = 1; i < n.size()-1; i++){
            if((n[i]-48)%2 == 0){
                status = 2;
            }
        }
    }
    return status;
}

int main() {
    // Test Case 1
    string n1 = "386467";
    // checking that number is itself even
    //  if yes 0 steps will be required
    int ans1 =  getDigit(n1);
    if(n1[n1.size()-1] % 2 == 0 || n1.size() == 0) cout << 0;
    else cout << ans1;
    cout << endl;

    // Test Case2
    string n2 = "399";
    int ans2 =  getDigit(n2);
    if(n2[n2.size()-1] % 2 == 0 || n2.size() == 0) cout << 0;
    else cout << ans2;
    cout << endl;

    return 0;
}

Output:

2

-1

Time Complexity: O(logn), n = number

Auxiliary Space: O(1)